Identify the basic operations and construct a recurrence relation C(n) that characterizes the time complexity of the algorithm. Determine the order of
growth for C(n) either solving the recurrence relation or using the Master
Theorem if appropriate. You may assume that n = 2k for some integer k.
Foo6 (n)
// Description: …
// Input: a positive integer n
// Output: …
if n = 0
return 1
if n = 1
return 2
else if n % 2 = 1
return Foo6(n/2) * Foo6(n/2) * 2
else
return Foo6(n/2) * Foo6(n/2)