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

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

  If f(n) = (nc) where c < Logba then T(n) = (nlogba)

So O(nlog32)=O(n0.632)

O(nlog32)

2)Number of times A is printed (n/3)n/3

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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