0

hello,

i have a problem in understanding time complexity.

i know that if we are having on for loop. for e.g.

for(int i=0.i<n;i++)
{
}
then my time complexity will be O(n).
And if i nest two for loops ,like this
   for (int i=0;i<n-1;i++)
     {
      for(int j=i;j<n;j++)
       {
       }
      }

time complexity will be O(n^2).

My question is what if my function has two for loops one after another like this:

for(int i=0;i<n;i++)
        {
         }
    for(int j=0;j<n;j++)
         {
          }

then what will be time complexity of my whole code now?

Please explain!!!

Edited by peter_budo: Keep It Organized - For easy readability, always wrap programming code within posts in [code] (code blocks)

3
Contributors
2
Replies
3
Views
7 Years
Discussion Span
Last Post by sainttt
1

Actually, the for loop

for(int i=0.i<n;i++) {...}

has complexity [TEX]\Theta(n)[/TEX]. It is true that it has complexity [TEX]O(n)[/TEX], but also that it has complexity [TEX]\Omega(n)[/TEX], and therefore by definition, it has complexity [TEX]\Theta(n)[/TEX].

As for the program containing the sequence of for loops

for(int i=0.i<n;i++) {...}
for(int i=0.i<n;i++) {...}

The running time complexity is the same as in the case for the single for loop. The reason for this can be found in the mathematical definition of these complexity classes.

In other words, the running time complexity for the 2 sequential for loops is [TEX]\Theta(2n) = \Theta(n)[/TEX].

Let me know if you need me to explain any of this in greater detail.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.