If given the following problem... $$4T \left(\frac n2\right) + c$$ after getting the pattern down you see the following $$4^k T\left(\frac {n}{2^k}\right) + 3^{k-1}c + 3^{k-2} c + \cdots + 3c + c$$
Then we factor out the common $c$ and determine it is a geometric series where $r>1$. So The following happens... $$\sum_{i=1}^n r^i = \theta(r^n)$$ So we apply this to the current equation I get this... $$4^k + c(4^{k-1} + 4^{k-2} + \cdots + 4 + 1)$$
So is the largest term $4^{k}$? If it is then, do ignore the resulting series? When I solve for $k$, I get $\log_2 n$ when stopping at $\frac {n}{2^k} = 1$. Then finally I plug this into the current problem and get this...$$4^{\log_2 n} + c(4^{\log_2 n -1} + 4^{\log_2 n - 2} + \cdots + 4 + 1)$$ Then I solve the issue with the non matching log base to below base and I get this $$4^{\log_2 n} = (2^{\log_2 4})^{\log_2 n}$$ which becomes the following $$n^{\log_2 4}$$ Is this correct? I get the run time as being either $\theta(n)$ or $\theta(n^{\log_2 4})$ . My guess is the time is still $\theta(n)$. Any thoughts?
You should get $$4^k~T(n 2^{-k}) + c(4^{k-1} + 4^{k-2} + \cdots + 4 + 1)$$
which for $k = \log_2(n)$ makes the leading term $4^k~T(1)$.
That depends on your initial conditions. If $T(1)>0$, then yes. Otherwise no.
But it doesn't matter anyway. The entire point of asymptotic runtime is that scaling factors don't affect asymptotic runtime behavior.
$$O(x^2) = O(4x^2) = O(100000000000000x^2)$$
Since $4^k$ and $4^{k-1}$ only differ by a factor of $4$, either could be considered the largest term in the sum for purposes of runtime analysis.
Keep in mind that $1 + x + x^2 + \dots + x^n$ is $\Theta(x^{n+1})$ for constant $x$. So you should get:
$$\Theta\left(T(1)~4^{\log_2(n) + 1}\right)$$ $$\Theta\left(4~T(1)~4^{\log_2(n)}\right)$$ $$\Theta\left(4~T(1)~n^{\log_2(4)}\right)$$
Removing constant factors:
$$\Theta\left(n^2\right)$$