How are the following equivalent to O(N)

Question

I am reading an example where the following are equivalent to O(N):

 O(N + P), where P < N/2
 O(N + log N)

Can someone explain in laymen terms how it is that the two examples above are the same thing as O(N)?

Answer 1

We always take the greater one in case of addition.

In both the cases N is bigger than the other part.

In first case P < N/2 < N

In second case log N < N

Hence the complexity is O(N) in both the cases.

Answer 2

Let f and g be two functions defined on some subset of the real numbers. One writes

f(x) = O(g(x)) as x -> infinite

if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)| <= M |g(x)| for all x > x0

So in your case 1:

f(N) = N + P <= N + N/2 

We could set M = 2 Then:

|f(N)| <= 3/2|N| <= 2|N| (N0 could any number) 

So:

N+p = O(N)

In your second case, we could also set M=2 and N0=1 to satify that:

|N + logN| <= 2 |N| for N > 1

Answer 3

Big O notation usually only provides an upper bound on the growth rate of the function, wiki. Meaning for your both cases, as P < N and logN < N. So that O(N + P) = O(2N) = O(N), The same to O(N + log N) = O(2N) = O(N). Hope that can answer your question.

Answer 4

For the sake of understanding you can assume that O(n) represents that the complexity is of the order of n and also that O notation represents the upper bound(or the complexity in worst case). So, when I say that O(n+p) it represents that the order of n+p.

Let's assume that in worst case p = n/2, then what would be order of n+n/2? It would still be O(n), that is, linear because constants do form a part of the Big-O notation.

Similary, for O(n+logn) because logn can never be greater than n. So, overall complexity turns out to be linear.

Answer 5

In short

If N is a function and C is a constant:

O(N+N/2):

If C=2, then for any N>1 :
    (C=2)*N > N+N/2,
    2*N>3*N/2,
    2> 3/2 (true)

O(N+logN):

If C=2, then for any N>2 :
    (C=2)*N > N+logN,
    2*N > N+logN,
    2>(N+logN)/N,
    2> 1 + logN/N (limit logN/N is 0),
    2>1+0 (true)

Counterexample O(N^2):

No C exists such that C*N > N^2 :
    C > N^2/N,
    C>N (contradiction).

Boring mathematical part

I think the source of confusion is that equals sign in O(f(x))=O(N) does not mean equality! Usually if x=y then y=x. However consider O(x)=O(x^2) which is true, but reverse is false: O(x^2) != O(x)!

O(f(x)) is an upper bound of how fast a function is growing. Upper bound is not an exact value.

If g(x)=x is an upper bound for some function f(x), then function 2*g(x) (and in general anything growing faster than g(x)) is also an upper bound for f(x).

The formal definition is: for function f(x) to be bound by some other function g(x) if you chose any constant C then, starting from some x_0 g(x) is always greater than f(x).

f(x)=N+N/2 is the same as 3*N/2=1.5*N. If we take g(x)=N and our constant C=2 then 2*g(x)=2*N is growing faster than 1.5*N:

If C=2 and x_0=1 then for any n>(x_0=1) 2*N > 1.5*N.

same applies to N+log(N):

C*N>N+log(N)
C>(N+logN)/N
C>1+log(N)/N
...take n_0=2
C>1+1/2
C>3/2=1.5

use C=2: 2*N>N+log(N) for any N>(n_0=2), e.g.

2*3>3+log(3), 6>3+1.58=4.68
...
2*100>100+log(100), 200>100+6.64
...

Now interesting part is: no such constant exist for N & N^2. E.g. N squared grows faster than N:

C*N > N^2
C > N^2/N
C > N

obviously no single constant exists which is greater than a variable. Imagine such a constant exists C=C_0. Then starting from N=C_0+1 function N is greater than constant C, therefore such constant does not exist.

Why is this useful in computer science?

In most cases calculating exact algorithm time or space does not make sense as it would depend on hardware speed, language overhead, algorithm implementation details and many other factors.

Big O notation provides means to estimate which algorithm is better independently from real world complications. It's easy to see that O(N) is better than O(N^2) starting from some n_0 no matter which constants are there in front of two functions.

Another benefit is ability to estimate algorithm complexity by just glancing at program and using Big O properties:

for x in range(N):
    sub-calc with O(C)

has complexity of O(N) and

for x in range(N):
    sub-calc with O(C_0)
    sub-calc with O(C_1)

still has complexity of O(N) because of "multiplication by constant rule".

for x in range(N):
    sub-calc with O(N)

has complexity of O(N*N)=O(N^2) by "product rule".

for x in range(N):
    sub-calc with O(C_0)
for y in range(N):
    sub-calc with O(C_1)

has complexity of O(N+N)=O(2*N)=O(N) by "definition (just take C=2*C_original)".

for x in range(N):
    sub-calc with O(C)
for x in range(N):
    sub-calc with O(N)

has complexity of O(N^2) because "the fastest growing term determines O(f(x)) if f(x) is a sum of other functions" (see explanation in the mathematical section).

Final words

There is much more to Big-O than I can write here! For example in some real world applications and algorithms beneficial n_0 might be so big that an algorithm with worse complexity works faster on real data.

CPU cache might introduce unexpected hidden factor into otherwise asymptotically good algorithm.

Etc...