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

Question

Talking about Big O notations, if one algorithm time complexity is O(N) and other's is O(2N), which one is faster?

Answer 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).