Member Avatar for drewangel

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 because: Keep It Organized - For easy readability, always wrap programming code within posts in [code] (code blocks)
  • 3 Contributors
  • 2 Replies
  • 76 Views
  • 2 Months Discussion Span
  • Latest Post Latest Post by sainttt
Member Avatar for galagatron

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.

Member Avatar for sainttt

plese explain the two deeply and clearly.......

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.