3
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.

Gaurav Kumar
  • 1,091
  • 13
  • 31
  • 4
    This is an instance of a function known as [tetration](https://en.wikipedia.org/wiki/Tetration). There is no solution using the functions we're most familiar with, so a new function must be defined: the [superlogarithm, or slog](https://en.wikipedia.org/wiki/Tetration#Super-logarithm). Therefore the answer is that the complexity of this is O(slog2 n). – President James K. Polk Dec 09 '19 at 00:11
  • Thanks for introducing me to this function. Happy to accept it as answer if you can post this as answer as this is exactly the answer I looked for. – Gaurav Kumar Dec 09 '19 at 04:47
  • 1
    note that `pow(2,i)` shouldn't be used unless i can be larger than 63. Use `1 << i` instead – phuclv Dec 09 '19 at 07:48
  • @JamesReinstateMonicaPolk nice catch and valid info in your comment but its not tetration due to wrong ending condition so no need for `slog` ... – Spektre Dec 09 '19 at 08:58
  • @phuclv 2^63 is indeed a big number, but it's reached after 5 iterations ... :-) – Déjà vu Dec 09 '19 at 09:37
  • @RingØ but there are a lot more things happen under the hood in `pow`, whereas `1ULL << i` works in a single cycle – phuclv Dec 09 '19 at 10:19
  • @phuclv [I heard](https://stackoverflow.com/questions/41072787/why-is-powint-int-so-slow/41072811#41072811) about that :-) – Déjà vu Dec 09 '19 at 12:42
  • @phuclv: But OP never specified a language, so you can't make a judgement as to whether `pow(2,i)` is *significantly* slower than a bit shift. – President James K. Polk Dec 09 '19 at 16:54
  • Now that all of you have mentioned, I see pow(2,i) could significantly have an impact on complexity, but original intention was to assume increment of i to be a constant time operation and then see the total work done inside the loop. Didn't know how to do the maths. Super algorithm is the way to do. It's more of a math problem for me than algorithm complexity. – Gaurav Kumar Dec 10 '19 at 04:06

1 Answers1

2

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)))
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • I don't really understand your argument that the ending condition means that this is not tetration. I have made no assumptions about the implementation. You are correct that any conventional bigint implementation would be swamped when the *exponent* reaches 2**65536. However, other representations are possible, including symbolic or a purely tetration notation. It's hard to tell if OP is using a code-like psuedo-code or actually has a real language in mind. – President James K. Polk Dec 09 '19 at 17:09
  • @JamesReinstateMonicaPolk I see it like: its more like the inverse of tetration (without outputting the result) its just like loop `k=0,1,2,3...` until `(2↑↑k)>n` if it would be direct tetration it would be ending with `k<=n` instead but for that the loop would need additional variable `k` as `i` is subresult. – Spektre Dec 09 '19 at 21:32
  • 1
    Unless I misunderstand the loop as it is currently written, after k iterations of the loop the value of i is `2↑↑k`. – President James K. Polk Dec 09 '19 at 23:46
  • 1
    @JamesReinstateMonicaPolk yes `~n=2↑↑k` but in this case the `k` is unknown and bound of `n` is known , the tetration has `k` known and `n` unknown ... – Spektre Dec 10 '19 at 04:22
  • 1
    I'm sure you're right but I just don't see it. Instead of bothering you continuously I'm just to going to stare at this until I understand. Thanks. – President James K. Polk Dec 10 '19 at 12:57
  • 1
    @JamesReinstateMonicaPolk :) heh know the feeling usually some sleep and or tea or something stronger helps ... if not and its not critical I usually drop such case down ... there are a lot of other interesting stuff out there no need to get stuck on single one ... – Spektre Dec 10 '19 at 20:05