I'm a complete beginner at this, and was having trouble with this problem.
looking at $T(n) = c(T(n/c) + 1)$. I'm pretty sure its in the form of
f(n) = af(n/b) + Cnd
I think the master theorem can be used to get the answer, but I'm not sure how to get the values to compare a to $b^{d}$
Here is what I know
a is the number of subproblems
n/b is the subproblem size
Cnd is the time to be spend during each recursion level (C is a constant)
I'm not sure how to apply this, or if it's the right solution.
Think about inputs of the form $c^k$. $$T(c^k)=cT(c^{k-1})+c=c^2T(c^{k-2})+c^2+c=\;...= c^kT(1)+c+c^2+c^3+...+c^k$$ $$T(c^k)=\frac{c\cdot c^k-1}{c-1}+c^kT(1)$$
If we want this function to be continuous, we note that $$T(n)=T(c^{\log_cn})=\frac{cn-1}{c-1}+T(1)n$$
If we let $a=T(1)+\frac 1{c-1}$ be an arbitrary constant, we get $$T(n)=an-\frac1{c-1}$$
This is the general form of the recursion. To find the specific form given your constraint, we substitute $T(1)=1$ into our equation for $a$, getting $a=1+\frac 1{c-1}=\frac c{c-1}$. So, the final solution is $$T(n)=\frac{c\cdot n-1}{c-1}$$
And, this function has complexity of $O(n)$ as it is a linear function.