Search code examples
algorithmrecurrencemaster-theorem

Solving Recurrence using Master Method

I'm trying to solve a recurrence relation to find out the complexity of an algorithm I wrote. This is the equation..

T(n) = T(n-1) + Θ(n)

And I found out the answer to O(n2), but I'm not sure if I did it right. Can someone please confirm?

Update: What if the equation is T(n) = T(n-1)+Θ(nlogn)? Will it still be O(n2)?

Solution

  • It is O(N)+O(N-1)+...+O(1) = O(N*(N+1)/2). So yes, the total complexity is quadratic.