I need to find the time complexity of the function in the picture using Master's Theorem.. I think the function is: T(n) = T(n-1) + c but it's impossible to solve using this theorem. Please help me I'm trying to solve it for 3 hours lol, thanks everyone! The function
1 Answers
The Master's theorem is for recurrences of the form T(n) = a*T(n/b) + f(n), where a >= 1 and b > 1 are constants.
Your recurrence is T(n) = T(n-1) + c, where c >= 1 is a constant.
n - 1 can't be put in the form n / b with b constant. So it's impossible to use Master's theorem here.
But it can be easily proved by induction that your recurrence gives T(n) = c * n as result.
Proof:
Let T(n) = c * n. You clearly have T(1) = T(0) + c = c * 0 + c = c , which is the base case.
Suppose it's valid for a given n, you have T(n+1) = T(n) + c = c * n + c = c * (n+1), so it's also valid for n + 1 and by induction it's valid for all natural number n.
Related