Big-theta bounds, algorithmic analysis

Question

I'm trying to learn how to find the big-theta bounds of various algorithms, but I'm having a hard time understanding how to do it, even after reading a number of questions here and lectures and textbooks on the subject. So for example

procedure for array a{
    step=1
    while(step <= n){
      i = n
      while(i >= step){
        a[i]= a[i-step] + a[i]
        i = i - 1}
      step = step * 2}
    }

I want to figure out the big-theta bound on the number of additions this goes through in terms of n, the number of indices in array a. I can see that the outer loop itself goes through log(n) iterations, but I can't figure out how to express what happens in the inner loop. Does anyone have an explanation or perhaps even a resource I might try consulting?

Answer 1

Big Theta notation asks us to find 2 constants, k1 and k2 such that our function f(n) is between k1*g(n) and k2*g(n) for sufficiently large n. In other words, can we find some other function g(n) that is at some point less than f(n) and at another point greater than f(n) (monotonically each way).

To prove Big-Theta, we need to find g(n) such that f(n) is O(g(n)) (upper bound), and f(n) is Big-Omega(g(n)) (lower bound).

Prove Big-O

In terms of Big-O notation (where f(n) <= g(n)*k), your algorithm, f(n), is O(log(n)*n), In this case g(n) = log(n) * n.

Let's prove this:

Find Inner Loop Executions

How many times does the outer loop execute? Track the "step" variable: Let's say that n is 100:

• 1
• 2
• 4
• 8
• 16
• 32
• 64
• 128 (do not execute this loop)

That's 7 executions for an input of 100. We can equivalently say that it executes (log n) times (actually floor(log n) times, but log(n) is adequate).

Now let's look at the inner loop. Track the i variable, which starts at n and decrements until it is of size step each iteration. Therefore, the inner while loop will execute n - step times, for each value of step.

For example, when n = 100

• 100 - 1 = 99 iterations
• 100 - 2 = 98 iterations
• 100 - 4 = 96 iterations
• 100 - 8 = 92 iterations
• 100 - 16 = 84 iterations
• 100 - 32 = 68 iterations
• 100 - 64 = 36 iterations

So what's our total iteration count of the inner loop?

1. (n-1)
2. (n-1) + (n-2)
3. (n-1) + (n-2) + (n-4)
4. (n-1) + (n-2) + (n-4) + (n-8)
5. etc.

How is this thing growing? Well, because we know the outer loop will iterate log(n) times, we can formulate this thing as a summation:

Sum(from i=0 to log(n)) n-2^i

= log(n)*n - Sum(from i=0 to log(n)) 2^i

= log(n)*n - (2^0 + 2^1 + 2^2 + ... + 2^log(n))

= log(n)*n - ( (1-2^log(n) ) / (1-2) ) (actually 2^log(n+1) but close enough)

= log(n)*n + 1 - n

So now our goal is to show that:

log(n)*n + 1 - n = O(log(n)*n)

Clearly, log(n)*n is O(log(n)*n), but what about the 1-n?

1-n = O(log(n)*n)?

1-n <= k*log(n)*n, for some k?

Let k = 1

1-n <= log(n)*n?

Add n to both sides

1 <= n*log(n) + n? YES

So we've shown that f(n) is O(n*log(n)).

Prove Big-Omega

Now that we have an upper bound on f(n) using log(n) * n, let's try to get a lower bound on f(n) also using log(n) * n.

For a lower bound we use Big Omega notation. Big Omega looks for a function g(n)*k <= f(n) for some positive constant k.

k(n*log(n)) <= n*log(n) + 1 - n?

let k = 1/10

n*log(n)/10 <= n*log(n) + 1 - n?

(n*log(n) - 10n*log(n)) / 10 <= 1 - n?

-9n*log(n)/10 <= 1 - n? Multiply through by 10

-9n*log(n) <= 10 - 10n? Multiply through by -1 (flipping inequality)

9n*log(n) >= 10n - 10? Divide through by 9

n*log(n) >= 10n/9 - 10/9? Divide through by n

log(n) >= 10/9 - 10/9n ? Yes

Clearly, the quantity log(n) grows larger as (10/9 - 10/9n) tends towards 10/9. In fact for n = 1, 0 >= 10/9 - 10/9. 0 >= 0.

Prove Big-Theta

So now we've shown that f(n) is Big-Omega(n*log(n)). Combining this with the proof for f(n) is O(n*log(n)), and we've shown that f(n) is Big-Theta(n*log(n))! (the exclamation point is for excitement, not factorial...)

g(n) = n*log(n), and one valid set of constants is k1=1/10 (lower bound) and k2 = 1 (upper bound).

Answer 2

To prove big-O: there are floor(log2(n)) + 1 = O(log(n)) iterations through the outer loop, and the inner loop iterates O(n) times per, for a total of O(n * log(n)).

To prove big-Omega: there are floor(log2(n/2)) + 1 = Omega(log(n)) iterations through the outer loop during which step <= n/2. The inner loop iterates n + 1 - step times, which, for these outer iterations, is more than n/2 = Omega(n) per, for a total of Omega(n * log(n)).

Together, big-O and big-Omega prove big-Theta.

Answer 3

Simplifying the representation of your code like the following, we can translate your code into Sigma notation

for (step = 1; <= n; step = step * 2) {
    for(i = n; i >= step; step = step - 1) {
    }
}

Like this: