CODEWITHSUNDEEP
c++calgorithmtime-complexitycomplexity-theory
LAK02
LAK02

Reputation: 21

Why is the time complexity of this code O(N)?

I thought the time complexity of the code below is O(n^2) or O(n*logn).

int j = 0;

for(i = 0; i < n; ++i) {
    while(j < n && arr[i] < arr[j]) {
        j++;
    }
}

However, the answer page says it is O(n).
I can't understand why it becomes so.
My (silly) opinions were the following:

  1. The time complexity is O(n^2) since there are two loop running n times. arr[i] < arr[j] may affect the while loop, but it doesn't matter.
  2. The time complexity is O(n*logn) since the while loop may run less than n times because arr[j] can be smaller than arr[i] during the loop. As a result, while loop would run for log(n) times.

Could you explain why was my answer wrong and why the correct time complexity is O(n)?

Upvotes: 1

Views: 425

Answers (2)

Jon Hanna
Jon Hanna

Reputation: 113312

for(i = 0; i < n; ++i)

Loops n times.

while(j < n && arr[i] < arr[j]) {
    j++;
}

Loops up to n times in total. Note that j is only ever incrementing for the entire loop of i, so it being an inner loop doesn't make it a higher order, as it still can only go from 0 to n for the entire set of loops.

So it's O(2n) = O(n)

Upvotes: 4

orip
orip

Reputation: 75457

In general, to understand the flow of something like this, try adding print statements to understand the flow, printing 'i' and 'j' at every point.

In this specific case, you know how many times the outer for loop is triggered, but try to see how many total times j can be incremented. Even though it's inside the for loop, its number of total iterations may be independent.

Upvotes: 0

Related Questions