CODEWITHSUNDEEP
big-o
Belphegor
Belphegor

Reputation: 1843

Confused about the time complexity of nested loops and looking for tips

Lets say I have two codes:

Code A:

for i = 0;
for j = 0;
while(i<n){       // O(n)
    while(j<n){   // O(n)
       printf("hello");
       .....

Running time = o(n) x O(n) = O(n^2)..

Code B:

int result = 0;
int i = 0;
while (i < n/2){    //O(n)
result += arr[i];
i += 1;
    while(i >= n/2 && i < n){   //O(n)
        results += arr[i];
        i +=1;
        }

Running time = O(n)

How come for Code B we DO NOT MULTIPLY the two O(n) to get O(n^2) like we did for Code A?? Very confused about how to determine running times.

Upvotes: 0

Views: 112

Answers (1)

chiwangc
chiwangc

Reputation: 3577

Let's give a run of code B in our head:

Suppose that n is quite large, say at least 100. Initially we have i = 0, so the condition for the outer loop is true, i will then increase by 1 due to line 5 (i += 1). So at this point we have i = 1, however in this case the condition the inner loop is false, so we just continue to the next turn of the outer loop.

The conditions for the outer loop and the inner loop remain to be true and false respectively until i becomes n/2 - 1, at this stage, the condition for the outer loop is true, and so i increases to n /2, and in this case the condition for the inner loop becomes true as well. So i will be increased up to n by the inner loop.

At last, we have i = n, the conditions for the loops are both false, and it will not loop further.

So the complexity is given below:

i          Work done
------------------------
0          1
1          1
2          1
.          .
.          .
.          .
n/2-2      1
n/2-1      n/2 + 1

So the total work done is:

(1 + n/2 - 2) * 1 + 1 * (n/2 + 1) = O(n)

Upvotes: 1

Related Questions