CODEWITHSUNDEEP
algorithmbig-o
You Ma
You Ma

Reputation: 189

Why codes that does N/2 steps are considered O(N)?

Consider a nested loop. The outer loop starts at i=0 and iterates N times, and the inner loop starts at j=i+1 and iterates up to j=N. So the inner loop will roughly do n/2 steps. At the end, however, the runtime is considered O(N2) Why is the inner loop considered O(N) and not O(N/2), since we have other codes that have O(log n) runtimes?

Upvotes: 0

Views: 89

Answers (2)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186813

It seems that you're mixing two different cases (division in the final formula - N**2/C - where C can be ignored: O(N**2/C) == O(N**2); and division in the loop: for (int j = N; j >= 1; j /= C) where C leads to logarithm):

 for (int i = 1; i <= N; ++i)
   for (int j = i + 1; j <= N; ++j) 
     SomeOperation(i, j);

Let's count the number of SomeOperation(i, j) to be performed:

 i    j
-------------------
 1    N - 1
 2    N - 2
 3    N - 3
..
 N    0

So we have 

(N - 1) + (N - 2) + ... + 2 + 1 + 0 ==
 N * (N - 1) / 2 == 
 N**2 / 2 - N / 2 ==
 O(N**2 / 2 - N / 2) == O(N**2 / 2) == O(N**2)

On the contrary (please, notice j /= 2 instead of ++j) which means far fewer inner loops

 for (int i = 1; i <= N; ++i)
   for (int j = N; j >= 1; j /= 2) 
     SomeOperation(i, j);

 i    j
-------------------
 1    log(N)
 2    log(N)
 3    log(N)
..
 N    log(N)

And here we have

 log(N) + log(N) + ... + log(N) ==
 N * log(N) == 
 O(N * log(N))

Upvotes: 2

ilim
ilim

Reputation: 4547

Big-O notation represents the complexity of time it takes a segment of code to execute, in proportion to some metric. Usually, the symbols used in braces represent quantities like input size, container size, etc.

In an intuitive sense, O(N) refers to the number of times a code runs in proportion to the symbols included inside the braces, as opposed to the exact number of times it runs. It may run K = N/2 times in reality, but the point Big-O notation tries to underscore is the fact that, the value of K is estimated by how large N is, and it is directly proportional to K.

To further clarify, notice that for a large enough N, the division by 2 does not really matter, as it is simply a constant factor. The notion that for a large enough N, constants are negligible is critical to understand to get a good grasp of various complexity notations, including Big-O.

Upvotes: 0

Related Questions