The recurrence I have is:
$$t(n) = n+ \sum_{i=1}^{k} t(a_in)$$
And I have two cases, (a) where $\sum_{i=1}^{k}a_i <1 $ and (b) where $\sum_{i=1}^{k}a_i =1 $
My question is, would both cases not result in $O(n)$?
My reasoning behind this is that for (a), $t(n)$ for some $n$ would be $n+ k$ numbers, ie $O(n + kc) = O(n)$.
For (b), it would be $n+kn$, ie $O(n+cn)=O(cn)=O(n)$.
I'm not sure if I'm right, but need some guidance either way.