2

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?

Imago
  • 2,132
Toni Ivanov
  • 63
  • 1
    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. – Imago Feb 13 '20 at 11:34

2 Answers2

2

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.$

River Li
  • 37,323
0

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

Daniel S.
  • 823