CODEWITHSUNDEEP
javabig-o
SkyZ
SkyZ

Reputation: 55

What are the Big O Notation for these for loops?

I am finishing up an assignment for my class, this particular section involves giving an "analysis" of the running time for several for loops. The instructor specified that he wants a Big Oh Notation answer.

I am building on the foundation that total running time is based on:

1)The cost of executing each statement
2)The frequency of execution of each statement
3)The idea of working from "inside and out", specifically starting from inner loops.

I know that:

total = 0;

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

Answer: O(N) its running linear.

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

Answer: O(N^2), we only care about how large N grows.

I am confused on 

for (int i = 0;i < n;++i)
     for (j=0;j < n * n;++j)
     ++total;

and

for ( i = 0;i < n;++i)
     for (j = 0; j < i;++j)
     ++total;

And last but not least, I am assuming from my textbook that all Triple nested loops are running at N^3 time?

Upvotes: 1

Views: 2708

Answers (1)

dfrib
dfrib

Reputation: 73176

You can analyze your algorithms using Sigma notation, to count/expand the number of iterations run by the inner for loop of your algorithms:

enter image description here

Where T_a covers

for (i = 0; i < n; ++i)
    for (j = 0; j < n * n; ++j)
        ++total;

and T_b:

for (i = 0; i < n; ++i)
    for (j = 0; j < i; ++j)
        ++total;

Finally, a note on your question:

"And last but not least, I am assuming from my textbook that all Triple nested loops are running at N^3 time?"

This is not true: it depends on how the iterate is increased as well as bounded in the signature of each loop. Compare e.g. with the inner loop in T_a above (bounded by n^2, but simply increased by 1 in each iteration) or e.g. the algorithm analyzed in this answer, or, for a slightly trickier case, the single loop analyzed in this answer.

Upvotes: 4

Related Questions