I got this question:
Func(n)
for (a = 1; a <= n; a = a * 2)
for (b = a; b <= n; b = b * 2)
print a + b
I understand the outside loop will run loglog(n), but I have some difficulty understanding how much the inside loop will run. And also what is the final answer to the Time complexity of this function. Thank you all.
Maybe listing down a couple of outputs may help. Here i give an example with n=10.
a=1: (1+1) (1+2) (1+4) (1+8)
a=2: (2+2) (2+4) (2+8)
a=4: (4+4) (4+8)
a=8: (8+8)
You can imagine this a square of edge roof(log(n)) or log(n) + 1 if n is an exact logarithm, that is not completely "filled". The number of items inside this square is almost the half of the area:
1/2 * log_2(n) * (log_2(n) + 1)
So this will be the asymptotic complexity of your program.