Consider the following functions. For each of them, determine how many times is ‘hey’ printed in terms of the input n. You should first write down a recurrence and then solve it using the recursion tree method. That means you should write down the first few levels of the recursion tree, specify the pattern, and then solve. (a) def fun(n) { if (n > 1) { print( ‘hi’ ‘hi’ ‘hi’ ) fun(n/4) fun(n/4) fun(n/4) }}

(b) def fun(n) { if (n > 1) { for i=1 to n { print( ‘hi’ ‘hi’ ) } fun(n/4) fun(n/4) fun(n/4) }}