Master Theorem applicable here?

Question

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

Answer 1

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

Answer 2

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(n²) then also T(n) = O(n²)

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