Algorithm Runtime

Question

I’m confused on the runtime for an if-statement and how to find it. This is my work so far, can someone explain what runtimes for if statements are like and how they work. 

Give an analysis of the running time (Big-Oh will do)

sum = 0; // O(1)

for( i = 1; i < n; ++i ) // O(N)

for( j = 1; j < i * i; ++j ) // O(N) * O(N) = O(N)

if( j % i == 0 ) //

for( k = 0; k < j; ++k ) //

++sum; // O(1)

Runtime =

Answer 1

sum = 0

will be executed O(1) times as you said

for( i = 1; i < n; ++i )

will be executed O(n) times as you said.

To be specific, the test inside the for statement will be executed O(n) times.

And the body will be executed for values of the variable i ranging as high as O(n).

for( j = 1; j < i * i; ++j )

The loop's initialization will be executed O(n) times.

It's test will be executed O(n)*O(n) times as you said (for each i),

but you also said that O(n)*O(n) = O(n), which is not true.

So in total, this loop's test will be executed O(n)*O(n)*O(n) times.

The body of the loop will executed with values of the variable j ranging as high as O(n)*O(n).

if (j%i == 0)

will be executed O(n)*O(n)*O(n) times.

But it will be true only O(n)*O(n) times.

The values of j in the then-clause can range as high as O(n)*O(n).

for( k = 0; k < j; ++k )

The initialization k=0 will be executed O(n)*O(n) times --

one per every execution of the then-clause.

The test k<j will be executed O(n)*O(n)*O(n)*O(n) times,

because j can range as high as O(n)*O(n).

++sum;

will be executed O(n)*O(n)*O(n)*O(n) times.