I'm finding my overthinking on solving what seems to be pretty easy complexity Questions. I was searching for some "method" when approaching this kind of questions. For example (pseudo code):
int func(int arr[], int n)
{
int i'
int a1, a2;
if (n<=1)
return arr[0];
a1 = func(arr, n-1);
a2 = 0;
for(i=2, i<=n; i*=i)
{
j = i
while(j>=i)
{
a2+=arr[j];
j/=2;
}
}
return a1+a2;
}
i = 1
while(i<n)
{
j = 1
while ( j < i^2)
j++;
i=i*2
}
for the second example, I understand the outer loop runs logn times. The inner loop, as a result runs : 1,...,(n/2)^2, n^2. so what the overall sigma should be?
The TL;DR:
Let's begin with the second example, rather than the first, because it turns out to be a lot simpler. Here's that second example:
i = 1
while(i<n)
{
j = 1
while (j < i^2)
j++;
i=i*2
}
I am going to assume here that i^2 means i2 rather than "i xor 2," but please correct me if I'm mistaken. :-)
This is a great place to introduce this maxim for working out big-O runtimes:
"When in doubt, work inside out."
That is, start with the innermost loop, work out its complexity, and replace the loop with something of the form "do X work." By repeating this process, you'll eventually figure out the overall runtime.
Here, our innermost loop is this one:
j = 1;
while (j < i^2)
j++;
How much work does this loop do? Well, we're counting up to i2, doing O(1) work per iteration, so this loop does Θ(i2) work. Notice that we're expressing the runtime in terms of i rather than, say, n, and that's intentional. The amount of work done here changes from iteration to iteration based on what the value of i is, and we're going to be as precise as possible.
Replacing that loop with "do Θ(i2) work" gives us this:
i = 1
while(i < n)
{
do Θ(i^2) work;
i = i * 2
}
Our next task is to see how much work is done with this simplified loop. First, let's see what values i takes on here. That's going to be 1, 2, 4, 8, 16, 32, ..., which is 20, 21, 22, 23, 24, 25, ... . More generally, after k iterations of the outer loop, we have i = 2k. Therefore, the work done by the loop is
(20)2 + (21)2 + (22)2) + (23)2 + (24)2 + ... + (2kmax)2
where kmax is the highest value of k for which the loop runs. Doing a bit of algebra here, notice that
(20)2 + (21)2 + (22)2) + (23)2 + (24)2 + ... + (2kmax)2
= (22)0 + (22)1 + (22)2 + (22)3 + ...(22)kmax
= 40 + 41 + ... + 4kmax
Using the formula for the sum of a geometric sequence, this simplifies down to
(4kmax + 1 - 1) / 3
= Θ(4kmax)
So all we need to do now is work out what kmax is and we'll have the total work done. To do that, notice that this loop stops running as soon as we overshoot n, which means that we're going to stop this loop when
n = 2kmax
lg n = kmax
This means that we'll have lg n iterations (here, lg n means log2 n) of the loop. Putting all this together, we have that the work done is
Θ(4kmax)
= Θ(4log2 n)
= Θ((22)log2 n)
= Θ(22 log2n)
= Θ(2log2n2)
= Θ(n2),
So our total work done is Θ(n2). Notice that we didn't get there by simply looking at the loops and saying something like "this loop runs this many times, and this loop runs this many times, so we just multiply them together." Instead, we had to do some math on sequences and series and slowly pull things apart to get to the result.
Now, let's move on to the second example:
int func(int arr[], int n)
{
int i;
int a1, a2;
if (n<=1)
return arr[0];
a1 = func(arr, n-1);
a2 = 0;
for(i=2, i<=n; i*=i)
{
j = i
while(j>=i)
{
a2+=arr[j];
j/=2;
}
}
return a1+a2;
}
For now, let's set the recursive part aside and just focus on the loops. The innermost loop is this one:
j = i;
while (j >= i)
{
a2 += arr[j];
j /= 2;
}
This loop is actually not that hard to reason about. Notice that the last step of the inner loop (j /= 2;) will decrease j so that it's less than i, and the loop will never run a second time. That means that the loop only does O(1) total work. We can therefore replace this loop with something like "do O(1) work" to get this:
int func(int arr[], int n)
{
int i;
int a1, a2;
if (n<=1)
return arr[0];
a1 = func(arr, n-1);
a2 = 0;
for(i=2, i<=n; i*=i)
{
do O(1) work;
}
return a1+a2;
}
Let's now focus on this loop:
for(i = 2; i <= n; i *= i)
{
do O(1) work;
}
How much work do we do here? The values that i takes on will be 2, 4, 16, 256, 65536, ... . We're looking for some sort of pattern here to see if we can work out the number of loop iterations performed. If we check out those values, we can see that they're equal to 21, 22, 24, 28, 216, etc. That in turn can be rewritten as 220, 221, 222, 223, 224, etc. In other words, we're looking at something doubly-exponential, and more specifically after k iterations the value of i is 22k.
This loop stops once we overshoot n, so we're looking for the value of k, the number of loop iterations, where 22k = n. Solving, we get that
22k = n
2k = lg n
k = lg lg n
So this loop runs for lg lg n iterations, each of which does O(1) work, so the total work done here is Θ(log log n). And that makes sense - if you repeatedly square a value, you can only do so O(log log n) times before you overshoot the number n.
We can then replace the loop with something like "do Θ(log log n)" work to get this:
int func(int arr[], int n)
{
if (n <= 1)
return arr[0];
func(arr, n-1);
do Θ(log log n) work;
return /* something */;
}
Progress! We now have a recursive function that does Θ(log log n) work, then calls itself with n decreased by one. Writing this out as a recurrence relation is a nice next step to try. Let's have T(n) denote how much work the function does when called with the parameter n. We then have that
T(n) = T(n - 1) + log log n
Why is this the recurrence that we get? Well, the work done when the input size is n is log log n, plus the amount of work required to evaluate the recursive call on n - 1. (I've dropped the Θ here just to make the math easier.)
We can iterate this recurrence a few times to see if we spot a pattern:
T(n) = T(n - 1) + log log n
= T(n - 2) + log log (n - 1) + log log n
= T(n - 3) + log log (n - 2) + log log (n - 1) + log log n
If we imagine carrying this out all the way to the end, we're left with something like
T(n) = log log 2 + log log 3 + log log 4 + ... + log log (n - 1) + log log n
So what does this simplify to? Well, we can get a nice conservative upper bound by noticing that
T(n) = log log 2 + log log 3 + log log 4 + ... + log log (n - 1) + log log n
≤ log log n + log log n + log log n + ... + log log n + log log n
= n log log n
= O(n log log n)
which gives and upper bound of O(n log log n) work. And we can do something similar for a lower bound:
T(n) = log log n + log log (n-1) + log log (n-2) + ... + log log (3) + log log 2
≥ log log n + log log (n-1) + log log (n-2) + ... + log log (n/2)
≥ log log (n/2) + log log (n/2) + log log (n/2) + ... + log log (n / 2)
= (n / 2) log log (n / 2)
= Ω(n log log n)
So the work done is Ω(n log log n). And since it's both O(n log log n) and Ω(n log log n), it works out to Θ(n log log n) work.
As you can see, there's a bunch of different techniques that come into play here:
I wish I could tell you there's a "simple" way to always figure out how much work a recursive function or loop nest takes, but alas, it's more of an art than a science. There are a bunch of common patterns that you'll learn to recognize with practice.