# Algorithm analysis of nested loop [duplicate]

so I have this code:

for (int i=1; i < n; i=i*5)
for (j=i; j < n; j++)
sum = i+j;


And I'm wondering, what's the time complexity of this for loop?

To start off, I know the first line is logn base 5, with an additional check to exit out of the for loop.

Then, for the second line, I have the following:

i = 1
j = 1, 2, 3,…, n        (n-5^0)+1
i = 5
j = 5, 6, 7, …, n       (n-5^1)+1
i = 25
j = 25, 26, 27,…, n     (n-5^2)+1
…
i = n
j = n                   (n-5^k)+1


But now, I'm stuck. Any help is appreciated.

## marked as duplicate by David Richerby, Rick Decker, Juho, hengxin, Luke MathiesonApr 19 '15 at 6:28

If you're interested in knowing the big-oh (O) then : logn (for first for statement) * (n-logn) times

Therefore, n*logn - log^2(n)

For big oh complexity, the complexity for above mentioned nested loops would be:

n*logn (since big-oh is only interested in larger values)

And as David motioned, that link has detailed explaination.

• But note that this isn't rigorous. At the first iteration of the outer loop, the inner loop runs $n-1 > n-\log n$ times. – David Richerby Apr 18 '15 at 12:31
• Hmn, that's true.. I guess I overlooked it. Thanks for pointing it out – random Apr 18 '15 at 12:34