Showing that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$

Solution 1:

After the inductive step we have:

$T(n) \le 2c(\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$

Note that $2 \lfloor \frac{n}{2} \rfloor \le n$ and we can get

$T(n) \le c(n + 34) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$

Expand to

$ T(n) \le cn\log (\lfloor \frac{n}{2} \rfloor + 17) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$

Now add and subtract $cn \log n$

$ T(n) \le cn \log n - cn \log n + cn\log (\lfloor \frac{n}{2} \rfloor + 17) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$

$ T(n) \le cn \log n + cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$

Now show the expression $cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n$ is negative for $n$ large enough and a correct choice of $c$ so that we can replace with

$ T(n) \le cn \log n$

Showing negativity

$cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n \le 0$

For large $n$, the first term $cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n})$ will be close to $cn\log(\frac{1}{2})$ which is negative. The other two terms are $O(n)$ so we hope we can choose a $c$ so that the first term can overtake the other two.

$cn\log (\frac{\lfloor \frac{n}{2} \rfloor + 17}{n}) + 34c\log (\lfloor \frac{n}{2} \rfloor + 17) + n \lt $

$cn\log (\frac{ \frac{n}{2} + 17}{n}) + 34c\log ( \frac{n}{2} + 17) + n = $

$cn\log (\frac{1}{2} + \frac{17}{n}) + 34c\log ( n (\frac{1}{2} + \frac{17}{n})) + n = $

$cn\log (\frac{1}{2} + \frac{17}{n}) + 34c\log n + 34c\log(\frac{1}{2} + \frac{17}{n}) + n = $

$cn\log (\frac{1}{2} ( 1 + \frac{34}{n})) + 34c\log n + 34c\log(\frac{1}{2}(1 + \frac{34}{n})) + n = $

$cn\log \frac{1}{2} + cn \log( 1 + \frac{34}{n}) + 34c\log n + 34c\log\frac{1}{2} + 34c\log(1 + \frac{34}{n}) + n \lt$

... now choosing any $ 0 < \epsilon \ll 1$ and $n$ large enough ...

$cn\log \frac{1}{2} + cn \epsilon + 34c\log n + 34c\log\frac{1}{2} + 34c\epsilon + n =$

$c(n\log \frac{1}{2} + n \epsilon + 34\log n + 34\epsilon) + 34c\log\frac{1}{2} + n \lt$

$c(n\log \frac{1}{2} + n \epsilon + 34\log n + 34\epsilon) + n $
Now note that $n\log \frac{1}{2} + n \epsilon + 34\log n + 34 \epsilon= n(\log \frac{1}{2} + \epsilon ) + 34 \log n + 34\epsilon \equiv g(n)$ is negative for large enough $n$ since we have a negative linear function competing with a postive $\log$ function.

It only remains to show we can choose $c$ such that for large enough $n$, $cg(n) + n \lt 0$

But we can do so, since $|g(n)| \in O(n)$, a $c$ exists such that it can outcompete the postive term $ n$

Solution 2:

Suppose $T(n) = 2T(\lfloor \frac{n}{2} \rfloor + 17) + n$ for all $n$ and that $T(n) = O(n \log n)$ for $n$ less than some bound $k$. Take $n = k > \lfloor \frac{n}{2} \rfloor + 17$, then we use the recursion:

$T(n) = 2T(\lfloor \frac{n}{2} \rfloor + 17) + n$

Since $T(n) = O(n \log n)$ for values smaller than $k$, there exists a constant $c$ such that $T(n) \leq c n \log n$. Therefore, $T(\lfloor \frac{n}{2} \rfloor + 17) \leq c (\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17)$.

Therefore, $T(n) \leq 2c (\lfloor \frac{n}{2} \rfloor + 17) \log (\lfloor \frac{n}{2} \rfloor + 17) + n$.

Now, with a little algebra we want to show that for the same constant $c$, this works out to $T(n) \leq c n \log n$.

Solution 3:

To show that T(n)=O(n log n) first assume that the result holds for all m

So assume that for all m< n, T(n)≤ c n log n

T(n)=2T(⌊n/2⌋+17)+n

    = 2c(⌊n/2⌋+17)log(⌊n/2⌋+17)+n

    = 2c(⌊n/2⌋+17)log(⌊n/2⌋+17)+n

now expand the above equation.

so T(n) = 2c⌊n/2⌋log(⌊n/2⌋+17) + 34clog(⌊n/2⌋+17) + n

but we know that, 2⌊n/2⌋ ≤ n, Therefore,

T(n) ≤ c nlog(2(⌊n/2⌋+17)/2) + 34c log(2(⌊n/2⌋+17)/2) + n

(We have multiplied and divided each term inside the log functions)

so, T(n) ≤ c nlog((n+34)/2) + 34c log((n+34)/2) + n

T(n) ≤ c nlog((n+34)/2) + 34c log((n+34)/2) + n

T(n) ≤ c nlog(n+34) + 34c log(n+34) + n + ( cn log(1/2)+ 34c log(1/2) )

T(n) ≤ c nlog(n+34) + 34c log(n+34) + n - ( cn + 34c )

by taking out n inside the statements in log functions,

T(n) ≤ c nlog(n(1+34/n)) + 34c log(n(1+34/n)) + n - ( cn + 34c )

T(n) ≤ c nlog(n) + c (n+34)log(1+34/n) + 34c log(n) + n - c(n + 34)

when n is very large (n goes to infinity 34/n goes to zero and (n+34) goes to n). Therefore,

T(n) ≤ c nlog(n) + c nlog(1) + n - cn

T(n) ≤ c nlog(n) - n (c-1)

So T(n) ≤ cn log(n) whenever c is greater than or equal to 1

Therefore the T(n)= O(nlogn)