Time Complexity for for loop with if-else block

user_12260444 0
Viewed 358

I want to find the time complexity for this below code. Here's my understanding-

The outer for loop will loop 2n times and in the worst case when i==n, we will enter the if block where the nested for loops have complexity of O(n^2), counting the outer for loop, the time complexity for the code block will be O(n^3).

In best case when i!=n, else has complexity of O(n) and the outer for loop is O(n) which makes the complexity, in best case as O(n^2).

Am I correct or am I missing something here?

for (int i = 0; i < 2*n; i++)
{
   if (i == n)
   {
      for (int j = 0; j < i; j++)
         for (int k = 0; k < i; k++)
            O(1)
   }
   else
   {
      for (int j = 0; j < i; j++)
         O(1)
   }
}
big-o time-complexity algorithm loops
4 Answers

No.

The question "what is T(n)?". What you are saying is "if i=n, then O(n^3), else O(n^2)". But there is no i in the question, only n.

Think of a similar question: "During a week, Pete works 10 hours on Wednesday, and 1 hour on every other day, what is the total time Pete works in a week?". You don't really answer "if the week is Wednesday, then X, otherwise Y". Your answer has to include the work time on Wednesday and on every other day as well.

Back in your original question, Wednesday is the case when i=n, and all other days are the case when i!=n. We have to sum them all up to find the answer.

user_14887990

This is a question of how many times O(1) is executed per loop. The time complexity is a function of n, not i. That is, "How many times is O(1) executed at n?"

  • There is one run of a O(n^2) loop when i == n.
  • There are (2n - 2) instances of the O(n) loop in all other cases.

Therefore, the time complexity is O((2n - 2) * n + 1 * n^2) = O(3n^2 - 2*n) = O(n^2).

I've written a C program to spit out the first few values of n^2, the actual value, and n^3 to illustrate the difference:

#include <stdio.h>

int count(int n){
 int ctr = 0;
 for (int i = 0; i < 2*n; i++){
    if (i == n)
      for (int j = 0; j < i; j++)
         for (int k = 0; k < i; k++)
            ctr++;
    else
      for (int j = 0; j < i; j++)
         ctr++;
 }
 return ctr;
}

int main(){
 for (int i = 1; i <= 20; i++){
  printf(
   "%d\t%d\t%d\t%d\n", 
   i*i, count(i), 3*i*i - 2*i, i*i*i
  );
 }
}

Try it online! (You can paste it into Excel to plot the values.)

user_42943990

The First loop is repeated 2*n times:

for (int i = 0; i < 2*n; i++)
{
    // some code
}

This part Just occur once, when i == n and time complexity is : O(n^2):

if (i == n)
{
    for (int j = 0; j < i; j++)
        for (int k = 0; k < i; k++)
            O(1)
}

And this part is depends on i.

else
{
    for (int j = 0; j < i; j++)
        O(1)
}

Consider i when:
i = 0 the loop is repeated 0 times
i = 1 the loop is repeated 1 times
i = 2 the loop is repeated 2 times
.
.
i = n the loop is repeated n times. (n here is 2*n)

So the loop repeated (n*(n+1)) / 2 times
But when i == n else part is not working so (n*(n+1)) / 2 - n and time complexity is O(n^2).

Now we sum all of these parts: O(n^2) (first part) + O(n^2) (second part) because the first part occurs once so it's not O(n^3).
Time complaxity is: O(n^2).

user_127275390

Based on @Gassa answer lets sum up all: O(n^3) + O((2n)^2) = O(n^3) + O(4n^2) = O(n^3) + 4*O(n^2) = O(n^3) Big O notation allows us throw out 4*O(n^2) because O(n^3) "eats" it

user_110612570
Related