Problem Set 2

Suppose the running time of an algorithm is governed by the recurrence 𝑇⁡(𝑛) =7 ∗𝑇⁡(𝑛3) +𝑛2. What’s the overall asymptotic running time (i.e., the value of 𝑇⁡(𝑛))?

• Θ⁡(𝑛2.81)
• Θ⁡(𝑛2)
• Θ⁡(𝑛2⁢log⁡𝑛)
• Θ⁡(𝑛⁢log⁡𝑛)

ANSWER: Applying the Master Method, 𝑎 =7,𝑏 =3,𝑑 =2,𝑎 <𝑏𝑑, case 2, work done at the root dominates the running time, therefore, running time is Θ⁡(𝑛2). Option 2 is correct.

Suppose the running time of an algorithm is governed by the recurrence 𝑇⁡(𝑛) =9 ∗𝑇⁡(𝑛3) +𝑛2. What’s the overall asymptotic running time (i.e., the value of 𝑇⁡(𝑛))?

• Θ⁡(𝑛3.17)
• Θ⁡(𝑛2⁢log⁡𝑛)
• Θ⁡(𝑛2)
• Θ⁡(𝑛⁢log⁡𝑛)

ANSWER: Applying the Master Method, 𝑎 =9,𝑏 =3,𝑑 =2,𝑎 =𝑏𝑑, work done at every level is the same, case 1, therefore, running time is Θ⁡(𝑛2⁢log⁡𝑛). Option 2 is correct.

Suppose the running time of an algorithm is governed by the recurrence 𝑇⁡(𝑛) =5 ∗𝑇⁡(𝑛3) +4⁢𝑛. What’s the overall asymptotic running time (i.e., the value of 𝑇⁡(𝑛))?

• Θ⁡(𝑛log⁡3log⁡5)
• Θ⁡(𝑛log3⁡5)
• Θ⁡(𝑛53)
• Θ⁡(𝑛2.59)
• Θ⁡(𝑛2)
• Θ⁡(𝑛⁢log⁡𝑛)

ANSWER: Applying the Master Method, 𝑎 =5,𝑏 =3,𝑑 =1,𝑎 >𝑏𝑑, work done = number of leaves, case 3, therefore, running time is Θ⁡(5log3⁡𝑛) =Θ⁡(𝑛log3⁡5). Option 2 is correct.

Consider the following pseudocode for calculating 𝑎𝑏 (where 𝑎 and 𝑏 are positive integers)

FastPower(a,b) :
  if b = 1
    return a
  else
    c := a*a
    ans := FastPower(c,[b/2])
  if b is odd
    return a*ans
  else return ans
end

Here [𝑥] denotes the floor function, that is, the largest integer less than or equal to 𝑥.

Now assuming that you use a calculator that supports multiplication and division (i.e., you can do multiplications and divisions in constant time), what would be the overall asymptotic running time of the above algorithm (as a function of 𝑏)?

• Θ⁡(log⁡𝑏)
• Θ⁡(√𝑏)
• Θ⁡(𝑏⁢log⁡𝑏)
• Θ⁡(𝑏)

ANSWER: Outside of recursion, we do constant work; each time, the input size is halved, therefore, 𝑎 =1,𝑏 =2,𝑑 =0,𝑎 =𝑏𝑑, case 2 of Master Method gives 𝑂⁡(𝑛𝑑⁢log⁡𝑛) =𝑂⁡(log⁡𝑛) =Θ⁡(log⁡𝑏) (input size is 𝑏 here). Option 1 is correct.

Choose the smallest correct upper bound on the solution to the following recurrence: 𝑇⁡(1) =1 and 𝑇⁡(𝑛) <𝑇⁡(⌊√𝑛⌋) +1 for 𝑛 >1. (Note that the Master Method does not apply.)

• 𝑂⁡(log⁡𝑛)
• 𝑂⁡(log⁡log⁡𝑛)
• 𝑂⁡(1)
• 𝑂⁡(√𝑛)

ANSWER: Substitute 𝑚 =log⁡𝑛 or 𝑛 =2𝑚, and 𝑆⁡(𝑚) =𝑇⁡(2𝑚)

𝑇⁡(2𝑚) <𝑇⁡(2𝑚2) +1
∴𝑆⁡(𝑚) <𝑆⁡(𝑚2) +1 (If this is unclear, let 𝑘 =𝑚2 and notice all we are doing is 𝑆⁡(𝑘) =𝑇⁡(2𝑘))
≤𝑆⁡(𝑚2) +1
𝑎 =1,𝑏 =2,𝑑 =0,𝑎 =𝑏𝑑, Master Method case 1, 𝑂⁡(log⁡𝑚) =𝑂⁡(log⁡log⁡𝑛). Option 2 is correct.