Consider this recursive function F, in which n/2 means the floor of n/2.

Recursive function F(n)

If (n 1) return 0

else return 1 + F(n/2)

end

Write a closed formula for the function computed by F.

Using the notation, give a formula for the running time of F.Each call to F counts as one time unit.

Use mathematical induction to prove both of your formulas.