# complexity analysis with recursive floor function

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

• 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?
– an4s
Commented Mar 22, 2021 at 15:36
• 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. Commented Mar 22, 2021 at 15:48
• @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$ Commented Mar 22, 2021 at 15:52
• 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?
– an4s
Commented Mar 22, 2021 at 20:28
• @an4s f(n) is defined as: $2f\left(\left\lfloor\dfrac n2\right\rfloor \right)+1$ , I hope it's clearer now (: Commented Mar 22, 2021 at 21:58

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

• 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 Commented Mar 23, 2021 at 11:45
• @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$.
– Karl
Commented Mar 23, 2021 at 16:50
• 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.
– Karl
Commented Mar 23, 2021 at 16:57