The Student Room Group

Complexity problem

N is some value

int sum = 0
for (int i = 1; i <= N*N; i = i*3)
sum = sum + 1


I am struggling with how to express this mathematically, in terms of N.

If the check was with just N (not N*N) then i incrementing by multiplication of 3 each time would mean would take cube root 3 iterations of N for outer loop?

But check is with N* N or N^2 so how do I express that?

If I play around with different values of N, say doubling each time, the i loop (on its own) doesn't grow by much. like logarithmic growth). How would I express this mathematically?
Original post by acomber
N is some value

int sum = 0
for (int i = 1; i <= N*N; i = i*3)
sum = sum + 1


I am struggling with how to express this mathematically, in terms of N.

If the check was with just N (not N*N) then i incrementing by multiplication of 3 each time would mean would take cube root 3 iterations of N for outer loop?

Successive i values will be

1,3,9,...3^(r-1) where r is the iteration number.

Loop terminates when 3r1N23^{r-1}\approx N^2

Quick Reply

Latest