Textbook : Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson,

Question

Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009

Show all work / explanations.

5. Try to analyze the following algorithm. Function Foo(n) if n > 1 then Print 'A Foo(n/3) for i from 1 to n do IPrint 'B' end Foo(n/3) end a) What is the running time of the function Foo(n)? Give detailed steps to obtain the asymptotic running time in big- notation. b) How many 'A's will be printed by Foo(n)? Give detailed steps to obtain your solution in big-O notation (in terms of n). Solution. Your solution here

Explanation / Answer

Answer a)

Running time of Foo(n)

T(n) = 2T(n/3) + n1

a = 2 , b = 3 , f(n) = n, c=1

now log32 < 1 means c > log32

Apply 3rd case of Master Theorem:- T(n)=f(n)

Hence by case 3 of Masters theorem we get the running time as (n)

Answer b)

Number of A depends on how many times the n>1 condition is satisfied
Number of A's = 2log3n - 1
Explanation:-

Take n = 3 , we get 2log33 - 1
=> 21 -1
=> 1
Take n = 27 , we get 2log327 - 1
=> 23 - 1
=> 7

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.