Q:

Time complexity for T(n-1)

I am confused on solving this time complexity problem.
T(n) = T(n-1)

I know in quick-sort worst case T(n) = T(n-1) + T(1) + n
Which evaluates to (n-1) + (n-2) + (n-3) + ... + 1 & this geometric sequence equals O(n^2)
However. I see answers on stackoverflow that say T(n) = T(n-1) + c = O(n).
How is this possible when this is also equal to (n-1) + (n-2) + (n-3) + ... + 1, which equals O(n^2)
Can somebody please explain.

A:

T(n) = T(n-1) + c isn't equal to (n-1) + (n-2) + (n-3) + ... + 1 because the terms being added are constants. Basically:
Adding nothing:
T(n) = T(n-1)
0 + 0 + 0 + ... + 0 = 0
O(1)

Adding a constant:
T(n) = T(n-1) + c
c + c + c + ... + c = nc
O(n)

Adding a variable:
T(n) = T(n-1) + n
1 + 2 + 3 + ... + n = n(n+1)/2
O(n^2)

