4
$\begingroup$

How can we prove that $T(n)=2T([n/2]+17)+n$ has a solution in $O(n \log n)$? What is the resulting equation I get after the substitution?

$$ T(n) = 2c \cdot \frac n2 \cdot \log \frac n2 + 17 + n $$

or

$$ T(n) = 2c \cdot \left(\frac n2 + 17\right) \cdot \log \left(\frac n2 + 17\right) + n $$

To me the first equation looks the correct, but the professor came to the second equation after the substitution. Which one of the two is correct, and how do I proceed in solving it (because that $17$ can be quite tricky)?

$\endgroup$
  • $\begingroup$ I'm not sure what substitution you're referring to here. But it's worth noting that case 2 in the Master theorem applies here and gives the desired result immediately. $\endgroup$ – Ayman Hourieh Mar 30 '13 at 16:20
  • $\begingroup$ Thanks for your answer Ayman. However we are suppose to solve this problem using induction a.k.a substitution method. $\endgroup$ – Peter Mar 30 '13 at 16:21
  • $\begingroup$ Both expressions are $O(n \log n)$. What substitution did you use? $\endgroup$ – Yoni Rozenshein Mar 30 '13 at 16:30
2
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Yea I got that far heh :) So first of all thanks for clearing out that the correct equation is the second one, after the inductive step has been applied. I guess the only missing piece for me is how to solve $\log (\lfloor \frac{n}{2} \rfloor + 17) + n$. $\endgroup$ – Peter Mar 30 '13 at 16:42
  • $\begingroup$ Try $\log (n + 34) = \log n + \log (1 + \frac{34}{n}) \leq \log n + \frac{34}{n}$ $\endgroup$ – Michael Biro Mar 30 '13 at 17:00
  • $\begingroup$ Are you sure you can do that? "Assume $g(n)=O(f(n))$ for $n \le k$" sounds like a bad idea. Because when you prove it for $f(n+1)$, you can get a bigger constant. I think the property you do the recurrence on should have the constant fixed. $\endgroup$ – xavierm02 Jul 2 '13 at 13:21
  • 1
    $\begingroup$ @Mark To be honest, more than 4 years later, I don't quite remember. :P I think it went something like this: We can safely suppose that $c > 2$ and the logarithm is in base $2$, then simplify $T(n) \leq 2c \left( \lfloor \frac{n}{2} \rfloor + 17 \right) \log \left( \lfloor \frac{n}{2} \rfloor + 17 \right) + n$ to $T(n) \leq c n \log n + 34c\log(n+34) - (c-1) n$. Then, note that if $n$ is large, (say $n > 1000$), this is less than $c n \log n$ no matter the value of $c > 2$, but for $n < 1000$, we can simply choose $c$ to be the max of the finite list of allowable $c$'s. $\endgroup$ – Michael Biro May 8 '17 at 0:31
  • 1
    $\begingroup$ @Mark I used $\lfloor \frac{n}{2} \rfloor + 17 \leq \frac{n + 34}{2}$, and tried to simplify, probably with some typos. You get $c(n+34)(\log (n + 34) - \log 2) + n = c (n + 34) \log(n +34) - c \log 2 (n + 34) + n$. Simplifying $\log (n + 34) \leq \log n + \frac{34}{n}$ gets $c n \log n + 34c( 1 + \log (n + 34) + \frac{n}{34c}) - c \log 2 (n + 34)$. The basic rule still applies, we add something that grows like $n$ and subtract something like grows like $(c \log 2)n $ for $c\log 2 > 1$. For large enough $n$, that's negative. $\endgroup$ – Michael Biro May 8 '17 at 4:10
1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ @Leucippus This clearly does provide an answer to the question. Question: How can we prove that $T(n)=2T([n/2]+17)+n$ has a solution in $O(nlogn)$. Last line of answer: "Therefore, the $T(n)=O(n\log(n))$". $\endgroup$ – user1729 Oct 17 '18 at 7:53
  • 1
    $\begingroup$ Incidentally, Sachith, it would improve your post greatly if you used MathJaX. See here for a tutorial: math.meta.stackexchange.com/questions/5020/… $\endgroup$ – user1729 Oct 17 '18 at 7:55
  • $\begingroup$ Thanks @user1729 .I'll use MathJax next time for sure! $\endgroup$ – Sachith Kasthuriarachchi Dec 3 '18 at 3:15

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