-1

I got this problem from Interview Bit

Problem

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

Question

The total number of comparisons that the while loop does is about n (probably less than or equal to n depending on arr). The loop runs n times. Shouldn't the time complexity be O(n^2)?

Alex
  • 2,369
  • 3
  • 13
  • 23

4 Answers4

5

One of the conditions in the while loop is while j < n. Meaning worst case, the code will only ever loop in the while loop n times regardless of how many loops the outer for loop does (j starts at zero and only increases, never resets to zero or decreases). Since the the for loop also loops n times, your big-O is O(n+n) => O(n)

NOTE: You can safely ignore the other condition arr[i] < arr[j], since we're just considering what the runtime would be in the worst-case.

dhuang
  • 909
  • 4
  • 18
3

This code looks like it was purposefully designed to be misleading. The while loop only runs once from 0 to n, and does not reset for every iteration of the outer for loop.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
  • Re: "The `while` loop only runs once from `0` to `n`": Well, *at most* once. It's also quite possible for `j` to never reach `n`. I'm not sure if the code was purposefully designed to be misleading; it's hard to tell at a glance what it's designed to do, but there may not be a much clearer way to do whatever-that-is. – ruakh Aug 10 '17 at 02:11
  • Addendum: I believe it finds the least element in the array (or the first least element if there's a tie) . . . which incidentally means that the `j < n` part isn't actually needed (I guess it's just an extra safety-check before accessing `arr[j]`. So, yeah, there's a clearer way to write this. – ruakh Aug 10 '17 at 02:14
3

You need to count the total number of times the statements in the innermost loop get executed.

The nested while loop does not contribute to the complexity because it goes through the values between 0 to n-1 only once, even though the steps through these values may be distributed among different iterations of the outer loop.

The innermost "payload" of the loop, i.e. arr[i] < arr[j] and j++, will execute at most n times, because incrementing j is a "one-way street": its value is never reset back to zero, so once j reaches n, the body of the loop no longer executes.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
1

Actually the inner loop is not dependent on 'i' ,so it will run maximum n times if 'i' goes from 0 to n-1.

The complexity would be O(n^2) if before while loop 'j' was initialised by 0, then in worst case for each 'i' while loop will execute 1+2+3+.......n-2 + n-1 times= O(n^2) when array elements are in descending order.

Prateek Mirdha
  • 67
  • 6
  • 1
    Note that value of j is not reset after each iteration, if j reaches n, it will do it only once. The complexity won't go above O(n). – Jonathan Darryl Aug 10 '17 at 10:07
  • 1
    Yes it is correct and that is what is written above that complexity would be O(n^2) "**IF**" 'j' were to be initialised before while loop.... – Prateek Mirdha Aug 11 '17 at 17:00