Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$f(n)=2f(\lfloor{n\over2}\rfloor)+1$ where $n$ is positive integer and $f:Z^+\to Z^+$. Prove that $f(n)=O(n)$.

Attempts: I have figured the case that for $n=2^k$, $f(n)=2n-1$ which can be obtainly by simple recurrance. But $n$ is any positive integer, i think only the case $n=2^k$ can't really help to the prove. Any hints or solution are welcome.

share|improve this question
    
Try showing that $f$ is monotone and that $f(2n)$ is not too much bigger than $f(n)$. –  Louis Feb 28 '13 at 9:55

4 Answers 4

Hint: Prove that if $2^k \leq n<2^{k+1}$, then $f(n)=2^kf(1)+2^k-1$ using induction.

share|improve this answer
    
how you do the induction?If n=r is true, how to procced to n=r+1? –  John Feb 28 '13 at 10:17
    
Induct on $k$, not $n$ –  Ivan Loh Feb 28 '13 at 10:38

Reading your attempt I assume that $f(1)=1$ but you might as well work with $f(1)$ being any other integer. Suppose $n= 2^k + l$ with $0\leq l<2^k$. Then $f(n)=2f(2^{k-1}+l_1)+1$ with $l_1\in\mathbb{Z}$ and $0\leq l_1\leq l/2<2^{k-1}$. By induction: $f(n)=2^k f(1)+2^{k-1}+\ldots+1=f(2^k)=2^{k+1}-1\leq 2n-1$.

share|improve this answer
    
the second sentence $f(n)=2f(2^{k-1}+l_1)+1$ is not true as you missed $\lfloor\rfloor$ –  John Feb 28 '13 at 10:00
    
@John: I just set $l_1=\lfloor l/2 \rfloor$, this makes the notation for the induction easier (You'll have $0\leq l_j<2^{k-j}$). –  Michalis Feb 28 '13 at 10:01

This is a very simple case of the Master theorem that can be solved exactly, the way that was done here. Let the binary representation of $n$ be given by $$ n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ Use $T(n)$ instead of $f(n)$ for consistency with some of the other SE material.

Now with $T(0)=0$, we have $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} (2^j \times 1) = 2^{\lfloor \log_2 n \rfloor+1} -1.$$

Observe that $$ \log_2 n - 1 < \lfloor \log_2 n \rfloor \le \log_2 n$$ so that $$n < 2^{\lfloor \log_2 n \rfloor+1} \le 2n \quad \text{and} \quad n-1 < T(n) \le 2n-1.$$ This allows us to conclude that $$T(n) \in \Theta(n).$$

share|improve this answer

Hint: Show that the property $f(n)\leqslant cn-1$ is hereditary, for every fixed positive $c$. Choosing $c$ large enough yields $f(n)=O(n)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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