Which algorithm is faster O(N) or O(2N)?

Solution 1:

The definition of big O is:

O(f(n)) = { g | there exist N and c > 0 such that g(n) < c * f(n) for all n > N }

In English, O(f(n)) is the set of all functions that have an eventual growth rate less than or equal to that of f.

So O(n) = O(2n). Neither is "faster" than the other in terms of asymptotic complexity. They represent the same growth rates - namely, the "linear" growth rate.

Proof:

O(n) is a subset of O(2n): Let g be a function in O(n). Then there are N and c > 0 such that g(n) < c * n for all n > N. So g(n) < (c / 2) * 2n for all n > N. Thus g is in O(2n).

O(2n) is a subset of O(n): Let g be a function in O(2n). Then there are N and c > 0 such that g(n) < c * 2n for all n > N. So g(n) < 2c * n for all n > N. Thus g is in O(n).

Typically, when people refer to an asymptotic complexity ("big O"), they refer to the canonical forms. For example:

• logarithmic: O(log n)
• linear: O(n)
• linearithmic: O(n log n)
• quadratic: O(n²)
• exponential: O(cⁿ) for some fixed c > 1

(Here's a fuller list: Table of common time complexities)

So usually you would write O(n), not O(2n); O(n log n), not O(3 n log n + 15 n + 5 log n).

Solution 2:

Timothy Shield's answer is absolutely correct, that O(n) and O(2n) refer to the same set of functions, and so one is not "faster" than the other. It's important to note, though, that faster isn't a great term to apply here.

Wikipedia's article on "Big O notation" uses the term "slower-growing" where you might have used "faster", which is better practice. These algorithms are defined by how they grow as n increases.

One could easily imagine a O(n^2) function that is faster than O(n) in practice, particularly when n is small or if the O(n) function requires a complex transformation. The notation indicates that for twice as much input, one can expect the O(n^2) function to take roughly 4 times as long as it had before, where the O(n) function would take roughly twice as long as it had before.