CODEWITHSUNDEEP
for-loopruntimebig-o
Yi Son
Yi Son

Reputation: 235

What is the running time of two separate for loops vs. two nested for loops?

In this example, I have two separate for loops. Is the running time O(num1 + num2)?

for(int i=0; i< num1 ; i++)     
{
   print i;
}

for(int i=0 ; i<num2 ; i++)
{
    print i;
}

And for this example, there is a nested for loop. Would the running time be O(num1*num2) because for each number in 0 to num1, you have to iterate from 0 to num2?

 for(int i=0 ; i<num1 ; i++)
 {
     for(int j=0 ; j<num2 ; j++)
     {  
         print i;
     }
}

Upvotes: 3

Views: 8421

Answers (1)

kronion
kronion

Reputation: 711

You can be more general. Big-O notation isn't about finding exact values given your actual parameters. It is about determining asymptotic runtime. In this case, we can just replace num1 and num2 with n, where n is the upper bound of some interval starting at 0. Using this method, we would find the runtime of your first example to be O(n), and the second example would have a runtime O(n^2). The first example runs in linear time, and the second example is quadratic. You rarely need to go into more detail than this to categorize algorithmic runtime.

Upvotes: 4

Related Questions