# Solving recursive function with floor

The recursive function is this: $$T(n) = \begin{cases} 2 & \text{ for }n=1;\\ T \left( \lfloor \frac{n}{2} \rfloor \right) + 7 &,\text{ otherwise} \end{cases}$$ Based on the definition of the function, the right side becomes:

$$T(n) = T( \lfloor \frac{n}{2^i} \rfloor) + 7 * i;$$

The procedure stops when $$\lfloor \frac{n}{2^i} \rfloor == 1$$

The problem is how do I continue it from there?

• What happens, if $2^i > n$ ? Do you know the logarithm function? Have you tried to find the values for some $n$, maybe up to $33$ ? Maybe you can spot a pattern. Feb 13 '20 at 11:34

We list first some terms: $$\underbrace{2}_{1}, \underbrace{9, 9}_{2}, \underbrace{16, 16, 16, 16}_{4}, \underbrace{23, 23, 23, 23, 23, 23, 23, 23}_{8}, 30, 30, \cdots$$ Conjecture: $$T(n) = 2 + 7\lfloor \log_2 n\rfloor, \quad n = 1, 2, 3, \cdots.$$ We need to prove it. To this end, let $$S(n) = 2 + 7\lfloor \log_2 n\rfloor, \quad n = 1, 2, 3, \cdots.$$ Let us prove that $$S(n) = T(n)$$ for $$n = 1, 2, 3, \cdots$$.

We use mathematical induction. First, $$S(1) = T(1) = 2$$, and $$S(2) = T(2) = 9$$.

Assume that $$S(k) = T(k)$$ for $$k = 1, 2, \cdots, n$$ ($$n\ge 2$$). We need to prove that $$S(n+1) = T(n+1)$$.

There exist integer $$m\ge 1$$ and integer $$r$$ with $$0\le r < 2^m$$ such that $$n = 2^m + r$$. We split into two cases:

1) $$r = 2^m - 1$$: We have $$S(n+1) = 2 + 7(m+1)$$ and $$S(\lfloor \frac{n+1}{2}\rfloor ) = 2 + 7m$$ which results in $$S(n+1) = S(\lfloor \frac{n+1}{2}\rfloor ) + 7 = T(\lfloor \frac{n+1}{2}\rfloor ) + 7 = T(n+1)$$.

2) $$r < 2^m - 1$$: We have $$S(n+1) = 2 + 7m$$ and $$S(\lfloor \frac{n+1}{2}\rfloor ) = 2 + 7(m-1)$$ which results in $$S(n+1) = S(\lfloor \frac{n+1}{2}\rfloor ) + 7 = T(\lfloor \frac{n+1}{2}\rfloor ) + 7 = T(n+1)$$. $$\quad$$ Q.E.D.

Thus, $$T(n) = 2 + 7\lfloor \log_2 n\rfloor, \quad n = 1, 2, 3, \cdots.$$

Your problem appears, for instance, in the analysis of binary search. The master method is helpful to solve the recursion.

https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

If $$\begin{equation} T(n) = T\left(\frac{n}{2}\right) + O(1) \end{equation}$$ then $$\begin{equation} T(n) \in O(\log n) \end{equation}$$ Apply Master theorem case $$c = \log_b a$$, where $$a = 1, b = 2, c = 0, k = 0$$

For more details, check http://www.math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf