CODEWITHSUNDEEP
algorithmbig-o
Tono Nam
Tono Nam

Reputation: 36048

Find the theta notation of the following recursive method

I have the homework question:

Let T(n) denote the number of times the statement x = x + 1 is executed in the algorithm

example (n)
{
    if (n == 1)
    {
       return
    }
    for i = 1 to n
    {
       x = x + 1
    }
    example (n/2)
}

Find the theta notation for the number of times x = x + 1 is executed. (10 points).

here is what I have done:

we have the following amount of work done: - A constant amount of work for the base case check - O(n) work to count up the number - The work required for a recursive call to something half the size

We can express this as a recurrence relation: T(1) = 1 T(n) = n + T(n/2)

Let’s see what this looks like. We can start expanding this out by noting that

T(n)=n+T(n/2)
=n+(n/2+T(n/4))
=n+n/2+T(n/4)
=n+n/2+(n/4+T(n/8))
=n+n/2+n/4+T(n/8)

We can start to see a pattern here. If we expand out the T(n/2) bit k times, we get: T(n)=n+n/2+n/4+⋯+n/2^k +T(n/2^k )

Eventually, this stops when n/2^k =1 when this happens, we have: T(n)=n+n/2+n/4+n/8+⋯+1

What does this evaluate to? Interestingly, this sum is equal to 2n+1 because the sum n+ n/2 + n/4 + n/8 +…. = 2n. Consequently this first function is O(n)

I got that answer thanks to this question answered by @templatetypedef

Know I am confused with the theta notation. will the answer be the same? I know that the theta notation is supposed to bound the function with a lower and upper limit. that means I need to functions?

Upvotes: 1

Views: 3500

Answers (1)

amit
amit

Reputation: 178431

Yes, the answer will be the same!

You can easily use the same tools to prove T(n) = Omega(n).

After proving T(n) is both O(n) [upper asymptotic bound] and Omega(n) [lower asymptotic bound], you know it is also Theta(n) [tight asymptotic bound]

In your example, it is easy to show that T(n) >= n - since it is homework, it is up to you to understand why.

Upvotes: 1

Related Questions