Let $T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\ 1 & \text{if }n=1 \end{cases}$

I need to prove that $t(n) \in O(n²)$, thus $t(n) \leq c\cdot n²$

I asked the question here and I got really great help last time, the thing is after I was shown last time that $f(n)=\log(n)\cdot\log(n!)$ is $\Theta(2\cdot\log(n)\cdot n) = \Theta(\log(n)\cdot n)$ I thought I could then use the master theorem

However since $a=\frac{2+\log n}{1+\log n}$ is NOT a constant I can not use the master theorem but I thought that I could use an upper bound for $a$, since $\frac{2+\log n}{1+\log n} < 2 \quad\forall n$ and then use the master theorem for $a=2$, $b=2$. But am I allowed to use the master theorem after finding an upper bound for the non-constant $a$?

What would other ways be to show that $T(n) = O(n^2)$ ?

  • $\begingroup$ Actually, $f(n) = \Theta(n\log^2 n)$. $\endgroup$ – Yuval Filmus May 27 '20 at 18:16
  • $\begingroup$ @YuvalFilmus: But isn't $\Theta(n \cdot log²n)$=$\Theta(n \cdot (logn)²)$ then with the law of logarithm $\Theta(n \cdot (logn)²)$ = $\Theta(n \cdot 2 \cdot (logn))$=$\Theta(n \cdot (logn))$? $\endgroup$ – Inocenciaa May 27 '20 at 18:47
  • $\begingroup$ No. It's not true that $(\log n)^2 = \Theta(\log n)$. $\endgroup$ – Yuval Filmus May 27 '20 at 18:49
  • $\begingroup$ You might be confused with $\log(n^2)$, which is $\Theta(\log n)$. However, $\log(n^2) \neq (\log n)^2$. For example, if logarithm is base 2 and $n = 2^m$, then $\log(n^2) = 2m$ while $\log^2 n = m^2$. $\endgroup$ – Yuval Filmus May 27 '20 at 18:50
  • $\begingroup$ @YuvalFilmus: Oh you are completely right! Thanks. But then it would be the second case here csd.uwo.ca/~mmorenom/CS433-CS9624/Resources/master.pdf. with (a,b = 2 and k=2) and $T(n)=\Theta(n*(log(n)^3)$? How could I then show that $T(n)=\Theta(n²)$? $\endgroup$ – Inocenciaa May 27 '20 at 19:28

Yes, you can define $T'(n) = 2 T'(\frac{n}{2}) + \Theta(n \log n)$, notice that $T(n) \le T'(n)$, and use the master theorem on $T'$ to obtain an upper bound of $O(n \log^2 n)$ to $T$.

Since for $n \ge 2$, $\frac{2+\log n}{1+\log n} \le \frac{3}{2}$ you can get a better upper bound by comparing $T$ to $$T'' = \begin{cases}\frac{3}{2}T''(\frac{n}{2}) + \Theta(n \log n) & \text{if $n\ge2$} \\ \Theta(1) & \text{otherwise}\end{cases}.$$ Applying the master theorem on $T''$ yields and upper bound of $O(n \log n)$ for $T$.

  • $\begingroup$ Thank you so much, for the answer. $\endgroup$ – Inocenciaa May 27 '20 at 18:49

Yes, you are allowed to use the master's theorem on upper bounds.

Formally, just define S(n) as the function which has the upper bounds (which recursive calls to itself) and use the master's theorem on S(n). you know that S(n) is a bound for T(n) (you can prove this in induction if you really want to) and thus if you managed to show that S(n) = O(n2) then also T(n) = O(n2)

Personally, i never explained why its possible to use the master's theorem on upper bounds too, and i have never seen anyone try to actually explain it before (since as you have seen from the explanation, the reason is pretty straightforward)

I Hope i managed to help :P

  • $\begingroup$ The master theorem doesn't apply directly. You need to couple the recurrence with another one which does have constant coefficients, as in Steven's answer. $\endgroup$ – Yuval Filmus May 27 '20 at 18:17
  • $\begingroup$ thank you for the explanation. $\endgroup$ – Inocenciaa May 27 '20 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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