Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009 Possible Chapters: 4.2 (Strassen's algorithm), 6 (Heapsort) , 7 (Quicksort), 22 (Graph Algorithms), 23 (Minimum Spanning Trees)

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