6

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)?

TMM
  • 9,976
Peter
  • 111

3 Answers3

4

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$

Mark
  • 5,696
1

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)

Sachith Kasthuriarachchi
  • 51
  • 1
    @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))$". – user1729 Oct 17 '18 at 07:53
  • 2
    Incidentally, Sachith, it would improve your post greatly if you used MathJaX. See here for a tutorial: https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference – user1729 Oct 17 '18 at 07:55
  • Thanks @user1729 .I'll use MathJax next time for sure! – Sachith Kasthuriarachchi Dec 03 '18 at 03:15
1

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

Michael Biro
  • 13,757
  • 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$. – Peter Mar 30 '13 at 16:42
  • Try $\log (n + 34) = \log n + \log (1 + \frac{34}{n}) \leq \log n + \frac{34}{n}$ – Michael Biro Mar 30 '13 at 17:00
  • 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. – xavierm02 Jul 02 '13 at 13:21
  • The constant $c$ is fixed - I just left some work to the OP - namely, computing how big $c$ needs to be. – Michael Biro Jul 02 '13 at 18:50
  • @MichaelBiro Can you look at my answer? I wonder if you were thinking of a much shorter way to do it because my way needs a lot of algebra, not a little like you were saying. I trust the due date for this homework has long passed so you needn't worry about giving OP "the answer". – Mark May 07 '17 at 03:29
  • 1
    @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. – Michael Biro May 08 '17 at 00:31
  • @MichaelBiro Thank you, could you elaborate on how the expressions inside the log? They were multiplied by two because it's okay to make the expression larger? But where did the negative part come from? – Mark May 08 '17 at 03:38
  • 1
    @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. – Michael Biro May 08 '17 at 04:10
  • That's great thanks very much! – Mark May 08 '17 at 05:05