The problem that I am struggling with is the recurrance relation
$T(n) = \lfloor(T(n/2))\rfloor + \lfloor(log \space n)\rfloor$ Where $T(1) = 1$
I am supposed to answer true/false to each of the following (along with explanation)
a) $\Omega(n^{(1/1000)})$
b) $O(n(log \space log \space n)^8)$
c) $\Theta(15log(5n^2))$
d) $O((log \space n)!)$
First, and perhaps someone could offer some clarification on my assumptions but I am taking $T(n) = T(n/2) + log \space n$ and just looking at terms of the type $2^n$ so as to simplify the calculations. The even numbers satisfy the original floor term of n/2 to give me whole numbers, and the terms of $2^n$ give me answers which increase linearly.
Now working out the recurrence relation by letting $n = 2^{m}$ I get:
$$T(2) = T(1) + log(2) = 1 + 1 = 2$$ $$T(4) = T(2) + log(4) = 2 + 2 = 4$$ $$T(8) = T(4) + log(8) = 4 + 3 = 7$$ $$\vdots$$
I end up with the following: $$T(2^n) = T(2^{n-1}) + log(2^n) = T(1) + log(2) + log(4) + log(8) + \ldots + log(2^{n})$$
However I see that since $log(2) = log(2^1) = 1log(2) = 1$, $log(4) = log(2^2) = 2log(2) = 2$ and in general $log(2^n) = nlog(2) = n$ that we just have a linear summation and thus we have $1 + \sum n$ over all the n terms. This is equal to:
$$1 + \frac{n(n + 1)}{2}$$
This however is $O(n^2)$ which is not correct for T(n) as if we look at the actual numbers $T(8) = 7 \lt 8$ and $T(16) = 11 \lt 16$ and so on such that $T(n) \lt n$.
So I am thinking that as we jumped by $2^n$ in the terms of the relation i.e. $T(n^2)$ that to get n back we would just take the log of that and so $log(n^2) = 2log(n)$ However we ignore the multiplier 2 (in all cases of looking at complexity bounds as it is just a constant), we have complexity class of $log(n)$
This answer however was based on my trying to get rid of the floors. I am wondering what the recurrence relation would look like in general - especially as I wonder if it is going to mess with any of the complexity classes for the questions a-d above.
Now for part a) I am thinking that $\Omega(n^{(1/1000)}) > log(n)$ as $n^{(1/1000)^{(1000)}} = n$ but $log(n^{1000}) = 1000log(n)$ and since we don't care about the 1000 as it is a constant we find that $\Omega(n) \gt \Omega(log(n))$ so $T(n) = \lfloor(T(n/2))\rfloor + \lfloor(log \space n)\rfloor$ is not bounded below by $n^{1/1000}$ and hence a) is false.
Thanks for your thoughts,
Brian
Did you study the Master Theorem yet? You here are in case 2, which gives $T(n)=\Theta(log^2 n)$ — meaning that answers (b) and (d) are correct.
Observe that once you get $T(2^n) = T(1) + \log 2 + \log 4 + \dots + \log 2^n$, you have $$ T(2^n) = \sum_{k=0}^n \log 2^k = \log \prod_{k=0}^n 2^k = \log 2^{\sum_{k=0}^n k} = \log 2^{n(n+1)/2} = \frac{n(n+1)}{2}\log 2 $$ so that, indeed, $T(m) =\Theta(\log^2 m)$ (as $T(2^n)=\Theta(\log^2 (2^n))$ — for the issue of the floors, see comment above).
Further, for (d), you have $(\log n)!=\prod_{k=1}^{\log n} k > \log n\cdot (\log n -1) \sim \log^2 n $, so $T(n) = O((\log n)!)$.