time complexity for for loop inside if which is inside another for loop

Question

for(int i=0;i<n;i++)
{
    if(i%2==0)
    {
        for(int j=i;j<n;j++)
             cout<<j;
    }
}

is the time complexity is O(n^2)?

In addition to @Kamesh: This is because constant factors are neglected in the **O** function (as they are of no interest). — Scheff's Cat, Jul 20 '17 at 12:02
@Scheff for small N constant factors can be much more important than the asymptotic complexity, so I wouldnt say that they are "of no interest" — 463035818_is_not_an_ai, Jul 20 '17 at 12:04
Their being "of no interest" is more of a reflection on the fact that you need to rely on the big-O notation with caution. It can be useful but does suffer from these obvious pitfalls. The comment @Scheff makes is valid. — Bathsheba, Jul 20 '17 at 12:06
@tobi303 Sorry, I didn't invent this principle - just learnt what was taught at university. May be, the reason is that: O function is used to predict how the increasing of input amount will cause the increase of effort (in time or memory space). — Scheff's Cat, Jul 20 '17 at 12:07
@Scheff the reason is that asymptotic complexity (the big O) just tells you what happens when N is increased to very big numbers. The limit above which it makes sense forget about any factors can be different for different algorithms. My comment was actually just refering to your wording: Asymptotic complexity ignores constant factors not because they are of no interest, but simply because asymptotic complexity is defined like this — 463035818_is_not_an_ai, Jul 20 '17 at 12:18
@tobi303 Sorry for my weak wording. I googled it before (to prevent writing something wrong) and found what I roughly remembered from the past. I would've cited my source but it's a German university site and I didn't take the time to find an English source. However, I believe, all this discussion has clarified it finally... — Scheff's Cat, Jul 20 '17 at 12:33

score 1 · Answer 1 · answered Jul 20 '17 at 12:01

1

Yes, the execution time is quadratic in n, so it's O(n²).

By the way, you could have written this as

for(int i=0;i<n;i+=2)
    for(int j=i;j<n;j++)
         cout<<j;

answered Jul 20 '17 at 12:01

Bathsheba

231,907
34
361
483

Here is a nice explanation for determine the time complexity: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm. – Andre Kampling Jul 20 '17 at 12:07

time complexity for for loop inside if which is inside another for loop

1 Answers1