I'm not sure if I should be posting this question here or under Stackoverflow, but given that it's algorithmic analysis, I figured Math was the right call. I have 2 functions that I'm trying to find the recurrence relation function to.
Function 1:
$T(2) = T(1)$
$T(4) = 2*T(2)$
$T(8) = 3*T(4)$
$T(16) = 4*T(8)$
$...$
$T(n) = log_2n*T(n/2)$
How is it derived that $T(n)$'s tightest bound is of time complexity $O((log_2n)!)$?
Function 2:
$T(2) = 2*T(1)$
$T(4) = 4*T(2)$
$T(8) = 8*T(4)$
$T(16) = 16*T(8)$
$...$
$T(n) = n*T(n/2)$
Would the tight bound for this be $O(n!)$ then?
We take $n$ to be a power of $2$. Now, in the first question we have the recurrence relation:
$$ T(n) = \log_2 n \cdot T\left( \frac{n}{2} \right) $$
We get, after expanding out the first few iterations:
$$ T(n) = \log_2 n \cdot \log_2 \left( \frac{n}{2} \right) \cdot \log_2 \left( \frac{n}{2^2} \right) \cdot \log_2 \left( \frac{n}{2^3} \right) \cdot ... \cdot T(2) $$
And from this we conclude:
$$ T(n) = \prod_{k = 0}^{\log_2 n} \log_2 \left( \frac{n}{2^k} \right) $$
Which can be rewritten as:
$$ T(n) = \prod_{k = 1}^{\log_2 n} \log_2 2^k = \prod_{k = 1}^{\log_2 n} k $$
And so we conclude:
$$ T(n) = \log_2 n ! $$
In the second question we have the recurrence:
$$ T(n) = n \cdot T\left( \frac{n}{2} \right) $$
We get, after expanding out the first few iterations:
$$ T(n) = n \cdot \frac{n}{2} \cdot \frac{n}{2^2} \cdot \frac{n}{2^3} \cdot ... \cdot T(2) $$
From which we conclude:
$$ T(n) = \prod_{k = 0}^{\log_2 n} \frac{n}{2^k} = \prod_{k = 1}^{\log_2 n} 2^k $$
Taking the logarithm base 2 of each side we get:
$$ \log_2 T(n) = \sum_{k = 1}^{\log_2 n} k = \frac{1}{2} (\log_2^2 n + \log_2 n) $$
Which means:
$$ T(n) = \sqrt{n}^{1 + \log_2 n} $$