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.

This is what I have so far:

runtime: log base 2 of n

Closed formula: F(n) = (the floor of log₂ n)

Base case: F(1) = log₂ 1= 0

Induction step:

Assume F(k) = log₂ k is true

Prove F(k+1) = log₂ (k+1)