def A (n): if n == 0: return 0 if n is even: return A (n/2)...

  

Transcribed Image Text:

def A (n): if n == 0: return 0 if n is even: return A (n/2) else: return A (2 (n-1)) + 1 (a) Prove that the A terminates when its input n is a nonnegative integer. (b) Write a recurrence for the running time (in terms of n) of A. (c) Give a closed form for its asymptotic running time (using whichever method you like) (d) If we look at the tree of recursive calls to A made by this algorithm, what is its depth (asymptotically, in terms of n)? How many leaves does it have (asymptotically, in terms of n)? (e) What function of n does A compute? It's easy to express it in terms of the binary expansion of n (i.e. the bits you get when you write n in base 2). def A (n): if n == 0: return 0 if n is even: return A (n/2) else: return A (2 (n-1)) + 1 (a) Prove that the A terminates when its input n is a nonnegative integer. (b) Write a recurrence for the running time (in terms of n) of A. (c) Give a closed form for its asymptotic running time (using whichever method you like) (d) If we look at the tree of recursive calls to A made by this algorithm, what is its depth (asymptotically, in terms of n)? How many leaves does it have (asymptotically, in terms of n)? (e) What function of n does A compute? It's easy to express it in terms of the binary expansion of n (i.e. the bits you get when you write n in base 2).