Confusion regarding while loop in for loop for time complexity

Question

I'm learning about time complexity and I understand the gist of it, but there's one thing that's really confusing me, it's about understanding the time complexity of a while loop in a for loop.

This is the code I am analyzing:

    sum := 0
    for i := 1 to n
       j := 1
       while j ≤ i
          sum += j
          j*=5
       end
    end

I've given a shot at this and I made this table, breaking it down:

CODE:	COST:	# OF TIMES:	TIME COMPLEXITY:
sum := 0	1	1	1
for i := 1 to n	int i = 1 (1)	1	2n+1
	i<=n (1)	n+1
	i++ (1)	n
j := 1	1	n	n
while j ≤ i	j ≤ i (1)	?	?
sum += j	1	?	?
j*=5	1	?	?
end	0	1	0
end	0	1	0

I understand the how the time complexity works for the for loop, but when I get to the while loop I'm confused.

I know that assignments have cost of 1 and comparisons have a cost of 1.

If the while loop was written as:

    sum:=0
    j:=1
    while j<=n
       sum+=j
       j*=5
    end

Since it's moving in increments of 5: (j*=5), its time complexity would be: log base5 n.

But the while loop in the code goes j<=i, which is throwing me off.

I someone could help me with cost/# of times the individual lines of the while loop, I would really appreciate it.

fyi: this isn't an assignment for school or anything like that, I'm genuinely trying to understand this concept for myself.

If the table above doesn't format correctly, here is a ss of it

Answer 1

Your loop is equivalent to the sum of log_5(i) for all i from 1 to n. The logarithm base doesn't matter, it's a constant; so i'll just say log from now on. This summation is asymptotically equal to n log n. Think about it this way: If you look at the graph of log, it's really, really flat, so most of the higher values in your summation look the same to the log function. This is only an intuition hint, not a formal proof, but it's sufficient. If you need a formal proof, check out this post