I'm try to find the solution to the recurrence
$T(n)=T(n/2)+T(n/4)+T(n/6)+T(n/12)+1$
I tried this,
if T(n) = O(n)
$
\begin{align}
T(n) &\le c(n/2)+c(n/4)+c(n/6)+c(n/12)+1 \\
&= cn+1 \\
&\le cn \ \ (not\ true)
\end{align}
$
if T(n) = O(nlogn)
$
\begin{align}
T(n) &\le c(n/2)log(n/2)+c(n/4)log(n/4)+c(n/6)log(n/6)+c(n/12)log(n/12)+1 \\
&= cnlogn - cnlogk + 1 \\
&\le cnlogn
\end{align}
$
But, answer is O(n)
Is it wrong?
So if $T(n) = cn - \frac 13$, then
$$T(n/2)+T(n/4) + T(n/6) + T(n/12) +1 = cn - \frac 43 + 1 = cn - \frac 13$$
Also, $T(0)$ is really $-\frac13$ from the recurrence.