What is the time complexity of this algorithm?
In the explanation below, I am assuming that all arithmetic and comparison operations are O (1).
for i = 1 to n do
The following is repeated N times, making the part n *
in the solution.
j = 2
while j < i do
j = j * j
The above calculates the first number in the following sequence >= i
::
2 = 2^(2^0)
4 = 2^(2^1)
16 = 2^(2^2)
256 = 2^(2^3)
65536 = 2^(2^4)
...
So the only thing you need to do is find the relationship between i and 2 ^ (2 ^ i). And log(log(2^(2^i))) = log(2^i) = i
.
source to share
Let me break it down and work from the inside out.
Imagine the following:
j = 2
while j < n do
j = j * 2
j
goes 2, 4, 8, 16 ... so if n
doubles in size then j
it only takes one iteration to beat it. This is basically the definition of logarithmic.
The inner loop is slightly different in your case:
j = 2
while j < n do
j = j * j
Now j
comes 2, 4, 16, 256, 65536 ... and much easier n
. In the first case, it j
grew exponentially per iteration, now it doubles exponentially. But we are interested in the inversion - it j
outperforms n
log (log ( n
)) in steps .
Then the outer loop just means you do it n
once.
source to share