0
$\begingroup$

I have the following function:

$$f(n) = \begin{cases} k,& n = 1 \\ 2f\left(\left\lfloor\dfrac n2\right\rfloor \right)+1, & n > 1 \end{cases}$$ I have to prove that for every $k>0$ we get $f(n)=\Theta(n)$.

So I managed to prove that $f(n)=O(n)$, but I'm having trouble proving the lower bund. I tried to claim $f(n)\geq0.5kn$ for all $k>0$ using induction. base case would be $k=1$ so $f(1)=k\geq0.5k$ and then after assuming the induction hypothesis the step will be: $f(n)=2f(\left \lfloor \frac{n}{2} \right \rfloor)+1\geq 2(0.5k\cdot\lfloor \frac{n}{2}\rfloor)+1\geq k\cdot\lfloor \frac{n}{2}\rfloor+1\geq k\frac{n}{2}$

but I suppose the last step is illegal since adding 1 to floor of n/2 won't necessarily be greater than 1. thanks in advance.!

$\endgroup$
6
  • $\begingroup$ Hint: try writing out $\left\lfloor\dfrac n2\right\rfloor$ (and, by extension, $\left\lfloor\dfrac n2\right\rfloor + 1$) for a few $n$s. Do you see a pattern? $\endgroup$
    – an4s
    Commented Mar 22, 2021 at 15:36
  • 1
    $\begingroup$ Is it $2f\left(\left\lfloor\frac{n}2\right\rfloor+1\right)$, as in the definition of $f$, or $2f\left(\left\lfloor\frac{n}2\right\rfloor\right)+1$, as in your subsequent computations? By the way, the version in the definition says that $f(2)=2f(2)$, which implies that $f(2)=0$, and one can then prove that $f(n)=0$ for all $n>1$, contradicting the result that you’re to prove. $\endgroup$ Commented Mar 22, 2021 at 15:48
  • $\begingroup$ @BrianM.Scott sorry for misleading you guys, I edited the question and fixed my proof, still there is a problem claiming $k\cdot floor(n/2)+1\geq kn/2$ $\endgroup$
    – perplexed
    Commented Mar 22, 2021 at 15:52
  • $\begingroup$ I am still unclear on what the definition of $f(n)$ is (thanks to Brian for pointing this out). At the top, you write $f\left(\left\lfloor\dfrac n2\right\rfloor + 1\right)$ but then later you write $f\left(\left\lfloor\dfrac n2\right\rfloor\right) + 1$. Could you please clarify this? $\endgroup$
    – an4s
    Commented Mar 22, 2021 at 20:28
  • $\begingroup$ @an4s f(n) is defined as: $2f\left(\left\lfloor\dfrac n2\right\rfloor \right)+1$ , I hope it's clearer now (: $\endgroup$
    – perplexed
    Commented Mar 22, 2021 at 21:58

1 Answer 1

1
$\begingroup$

We want a bound of the form $f(n)\ge An$ and will use $\lfloor x\rfloor>x-1$ to get rid of the floor function. So the induction step looks like: $$ \begin{align} f(n) &=2f\left(\left\lfloor \frac n2\right\rfloor\right)+1\\ &\ge2A\left\lfloor \frac n2\right\rfloor+1\\ &>2A\left(\frac n2-1\right)+1\\ &=An+1-2A\\ &\ge An \end{align} $$ where the last step works as long as $A\le\frac12$. For the base case, you need $A\le k$, so take $A=\min(k,\frac12)$.

Alternatively, an exact solution is $f(n)=2^{\lfloor\log_2n\rfloor}(k+1)-1$. This formula can be proved straightforwardly by induction, using that $\left\lfloor\log_2\left\lfloor\frac n2\right\rfloor\right\rfloor+1=\lfloor\log_2n\rfloor$. To see this fact, let $r=\lfloor\log_2n\rfloor$ so that $n\in[2^r,2^{r+1})$, so $\frac n2\in[2^{r-1},2^r)$, so in fact $\left\lfloor\frac n2\right\rfloor\in[2^{r-1},2^r)$, so $\left\lfloor\log_2\left\lfloor\frac n2\right\rfloor\right\rfloor=r-1$.

Then it's clear that $f$ is $\Theta(n)$, since $\frac {n+1}2\le2^{\lfloor\log_2 n\rfloor}\le n$, and each $\le$ is actually an equality for infinitely many $n$. The graph of $f$ consists of horizontal lines through the region bounded by the lines $y=(k+1)\frac{x+1}2-1$ and $y=(k+1)x-1$.

$\endgroup$
3
  • $\begingroup$ But is it ok to make the assumption that A=min(k,0.5)? then it makes k a specific valued and we should prove it for all k>0 $\endgroup$
    – perplexed
    Commented Mar 23, 2021 at 11:45
  • $\begingroup$ @Somuser yes, it's ok. The slope of the bounding line depends on the parameter $k$ (just like with your attempt of $A=0.5k$). We just need to ensure that $A>0$ when $k>0$. $\endgroup$
    – Karl
    Commented Mar 23, 2021 at 16:50
  • $\begingroup$ Note that I organized the answer to show how to figure out which $A$ will work, but now that we know it, you could instead start the proof with "Let $A=\min(k,\frac12)$" to make the logical structure simpler. $\endgroup$
    – Karl
    Commented Mar 23, 2021 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .