CODEWITHSUNDEEP
algorithmmathtime-complexityexponentiation
Gaurav Kumar
Gaurav Kumar

Reputation: 1091

Time complexity of a loop with value increasing in powers of 2

for(i=1;i<=n;i=pow(2,i)) { print i }

What will be the time complexity of this?

Approximate kth term for value of i will be pow(2,(pow(2,pow(2,pow(2, pow(2,pow(2,...... k times)))))))

How can the above value, let's say kth value of i < n be solved for k.

Upvotes: 3

Views: 1699

Answers (1)

Spektre
Spektre

Reputation: 51835

What you have is similar to tetration(2,n) but its not it as you got wrong ending condition.

The complexity greatly depends on the domain and implementation. From your sample code I infer real domain and integers.

This function grows really fast so after 5 iterations you need bigints where even +,-,*,/,<<,>> are not O(1). Implementation of pow and print have also a great impact.

In case of small n<tetration(2,4) you can assume the complexity is O(1) as there is no asymptotic to speak of for such small n.

Beware pow is floating point in most languages and powering 2 by i can be translated into simple bit shift so let assume this:

for (i=1;i<=n;i=1<<i) print(i);

We could use previous state of i to compute 1<<i like this:

i0=i; i<<=(i-i0);

but there is no speedup on such big numbers.

Now the complexity of decadic print(i) is one of the following:

O( log(i))               // power of 10 datawords (like 1000000000 for 32 bit)
O((log(i))^2)            // power of 2 datawords naive print implementation
O( log(i).log(log(i)))   // power of 2 datawords subdivision or FFT based print implementation

The complexity of bit shift 1<<i and comparison i<=n is:

O(log(i))                // power of 2 datawords

So choosing the best implementation for print in power of 2 datawords lead to iteration:

O( log(i).log(log(i) + log(i) + log(i) ) -> O(log(i).log(log(i)))

At first look one would think we would need to know the number of iterations k from n:

n = tetration(2,k)
k = slog2(n)

or Knuth's notation which is directly related to Ackermann function:

n = 2↑↑k
k = 2↓↓n

but the number of iterations is so small in comparison to inner complexity of the stuff inside loop and next iterations grows so fast that the previous iteration is negligible fraction of the next one so we can ignore them all and only consider the last therm/iteration...

After all these assumptions I got final complexity:

O(log(n).log(log(n)))

Upvotes: 2

Related Questions