# 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

• 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