Time complexity where one loop repeatedly squares a value and one repeatedly multiplies by three?

user_10286691 0
Viewed 177

I need a way to calculate Big-theta bound for the following loop and I'm not sure I can find a pattern:

public static in sumCalc(int n) {
  int k=3;
  int sum =0;
  while (n>0) {
     for (int i=2; i<k; i=i*i)
       sum = sum+i
     n--
     k=k*3
  }
  return sum;
}

I can see that outer loop will execute for n times, but harder to find how many times will the inner loop will execute. I tried to find a pattern by tracing it and came up with something like this:

   n value   k value     #of times inner loop executes
--------------------------------------------------------
   n         k=3         1
   n-1       k=3^2       2
   n-2       3^3         3
   n-3       3^4         3
   n-4       3^5         3
   n-5       3^6         4
   ...
   n-9       3^10        4
   n-10      3^11        5
   ...

I am not sure there is a pattern here. I am unable to write sum formula to calculate total execution of the inner loop from this table. Intuitively, I m thinking outer loop will execute O(log n) times and the inner will execute O(sqrt(n)). So the answer can be O(sqrt(n)*log n) ?

big-o for-loop algorithm
1 Answers

This is an interesting one! To work through it, we’ll need a few mathematical tools, but most importantly we’ll need this maxim:

When in doubt, work inside-out!

That is, let’s take the innermost loop, figure out how much work it does, then repeatedly remove it and replace it with a placeholder indicating how much work is done.

Our innermost loop looks like this:

for (int i=2; i<k; i=i*i)
   sum = sum+i

The inside of this loop does O(1) work, so all we need to do is figure out the number of iterations. That boils down to this question: how many times can you square a number (starting at 2) before you overshoot some number k?

To work out the answer, let’s imagine we’re on the jth iteration of the loop. What’s the value of i at this point? Well,

  • At the start of the first iteration (j = 0), i = 2 = 21.
  • At the start of the second iteration (j = 1), i = 4 = 22.
  • At the start of the third iteration (j = 2), i = 16 = 24.
  • At the start of the fourth iteration (j = 3), i = 256 = 28.

Notice a pattern? Every time we square i, we’re doubling the exponent on the power of two. That means that the exponent itself is growing exponentially, and that’s easier to see if you write out the numbers like this:

  • At the start of the first iteration (j = 0), i = 2 = 21 = 220.
  • At the start of the second iteration (j = 1), i = 4 = 22 = 221.
  • At the start of the third iteration (j = 2), i = 16 = 24 = 222.
  • At the start of the fourth iteration (j = 3), i = 256 = 28 = 223.

More generally, on iteration j of the loop, the value of i is 22j. And the loop will keep running until the corresponding value of j ends up overshooting k. Solving, we get this:

22j = k

2j = lg k

j = lg lg k

In other words, this loop will run Θ(log log k) times. That’s an incredibly small number of times, and you need k to be staggeringly huge to get this to run any reasonable number of iterations. For reference, lg lg A, where A is the number of particles in the known universe, is around 8.

As a note, seeing log log here isn’t unexpected. If you repeatedly add one to a quantity, it’ll take you O(k) iterations to overshoot the number k. If you repeatedly double a number until you overshoot the number k, it’ll take you O(log k) iterations to do so. And if you repeatedly square a number k, it’ll take you O(log log k) iterations to do so.

So if we jump back to the original code, we can remove and rewrite that inner loop like this:

  int k=3;
  while (n>0) {
     do Theta(log log k) work;
     n--;
     k=k*3;
  }

So what now? Well, we know this outer loop will run n times. But what’s the total work done? We can see that the values of k taken on here grow exponentially quickly: k is 3 on the first iteration, then 9 on the second, then 27 on the third, etc. More generally, it takes on the value 3j on iteration j. That means we can sum up the work done by this while loop by adding up log log k for all the values that k takes on. That gives the following:

log log 3 + log log 32 + log log 33 + ... + log log 3n

= log log 3 + log (2 log 3) + log (3 log 3) + ... + log (n log 3) (power rule for logarithms)

= log((log 3) · (2 log 3) · (3 log 3) · ... · (n log 3)) (sum rule for logarithms)

= log ((1 · 2 · 3 · ... · n)(log 3 · log 3 · log 3 ... · 3)) (regrouping terms)

= log (n! · (log 3)n (simplifying)

= log (n!) + n log log 3 (sum and power rules)

= Θ(n log n) + n log log 3 (Stirling’s approximation)

= Θ(n log n).

So the overall work done is Θ(n log n).

Now, one detail to note here is that this assumes that the values of k and i never overflow, which isn’t a safe assumption in general. In practice, this function will start acting weirdly for any reasonable value of n. But just for simplicity, we’ll ignore that for now. :-)

user_5015570
Related