CODEWITHSUNDEEP
algorithmcomplexity-theorytime-complexityasymptotic-complexity
Vlad
Vlad

Reputation: 1601

What is the complexity of this algorithm?

I need to calculate the complexity for this code. I understand that it is O(n), but I need an evidence in the formulas. For example, the loop has complexity 1 + 3*n + n*f(body).

Code 1:

int i = 0;
int t = 0;
int j = n/2;
while (i<n) {
    while (t<n/2) {
        t++;
        i++;
    }
    while (j<n) {
        j++;
        i++;
   }

}

UPD: I need to calculate the complexity for this code too. Is it difference from Code 1?

Code 2:

int k = 0;
int i = 0;
int t = 0;
int j = n/2;
while (i<n) {
    k=0;
    while ((t<n/2) && (k<=10)) {
         t++;
         i++;
         k++;
    }
    k=0;
    while ((j<n) && (k<=10)) {
         j++;
         i++;
         k++;
    }
}

Upvotes: 0

Views: 128

Answers (2)

Am_I_Helpful
Am_I_Helpful

Reputation: 19158

In t's while-loop, i is supposedly incremented from 0 to (n/2)-1 and in the next,j's while-loop, is incremented upto i

So,in one single iteration i is expected to execute the outer-loop!

Also,t's and j's while-loop execution are mutually exclusive to each other. But,they both commonly increment i---t from o to n/2 - 1 and j from n/2 to n-1.

Hence,the code complexity

= single-iteration of i-loop*(complexity of inner-while loops)

= O(1)*(complexity of t-based loop UNION complexity of j based loop)

= O(1) * ( O(n/2) UNION O(n/2) )

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

= O(n).

So,your conclusion was correct. This code's complexity is O(n)...

When talking about code 2,it is not-much different from code 1! Only a new variable k has been added which will cause the inner-loops to iterate only 10 times as it is bounded with && condition.

Also, the i-based loop will iterate for n/20 times as in 1 iteration of i-loop, the i is modified upto 20 after execution of both the inner-loops... Hence, i will complete its test of being lesser than n,after n/20 iterations. Hence, algorithmic performance of i-based loop= O(n/20)...

Hence,complexity of code 2

= multiple-iteration of i-loop*(complexity of inner-while loops)

= O(n/20) * ( O(1) UNION O(1) )
// inner-loops will run for 10 iterations and hence,their complexity comes out to be O(1).

= O(n).

Hence, the complexity for the code 2 will be O(n)...

Upvotes: 6

chettyharish
chettyharish

Reputation: 1734

The best way to understand (or calculate efficiency) when you are new to something is to try out some random values.

Assume that n = 100,

int i = 0;
int t = 0;
int j = n/2;

After these instructions, i=0 ; t = 0 and j = 50

while (i<n) {

States that the while breaks when i = 100. 

    while (t<n/2) {
             t++;
             i++;
        }

Since this loop runs from t =0 to t = 50 (50 times) , the final value of t = 50 and i = 50 (both are incremented)

    while (j<n) {
         j++;
         i++;
    }
}

Since this loop runs from j = 50 to j = 100 (50 times) , the final value of j = 100 and i = 100 (both are incremented)

So you can see that the first while loop "while (i

So to calculate the number of operations all we have to do is to multiply if loops are inside loops and add if they are at the same level. So here it is : (Run of outer loop) * (Run of inner loops) = 1 * (50 + 50) = 100. Notice this is equal to 100 (n) which we started from. So the program has a complexity of 1n i.e. O(n)

For any other instance , If we had the final answer as 500, then it would have been complexity of 5n i.e. still O(n)

You don't have to put numbers every time but whenever you are stuck this should give you an intuitive idea of how to solve such questions.

Upvotes: 1

Related Questions