2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Imago
    Feb 13 '20 at 11:34
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.