Converting a for loop to a sum

52 Views Asked by At

I'm trying to convert the following for loops to sums, but I'm getting a little confused about the upper limits:

  1. for(i=2; i <= n; i*=i)
  2. for(i=n; i > 1; i=sqrt(i))

We can suppose that each iteration does $\Theta(1)$.

So for 1 we have $\Large\displaystyle \sum_{i=0}^m 2^{2^i} $, and we want to know for what m we have $2^{2^m} <n$ so we get that $m=\log\log n$, is that right?

For 2, $\Large\displaystyle \sum_{i=0}^m n^{\frac 1 {2^i}} $, trying to use the same method, maybe since we want to find the smallest $i$ such that $\large n^{\frac 1 {2^i}}\ge2$ so we get that: $\log\log n \ge i$ so $m=\log\log n$ again?