2

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.

Khaled.K
  • 5,828
  • 1
  • 33
  • 51
user2158382
  • 4,430
  • 12
  • 55
  • 97

2 Answers2

9

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)
fgb
  • 18,439
  • 2
  • 38
  • 52
0
T(n) = T(n-1) -> T(n-1) = T(n-2) --> T(n) = T(0)

Which is 0 or O(1)

cgnorthcutt
  • 3,890
  • 34
  • 41
  • If this is true, then can you explain why `T(n) = a + T(n - 1)` is `O(n)`. According to http://stackoverflow.com/questions/13467674/determining-complexity-for-recursive-functions-big-o-notation – user2158382 May 15 '14 at 00:55
  • `T(n) = a + T(n - 1) = 2a + T(n - 2) = ka + T(n - k) = na + T(0)` which is `O(n)`. – Bruno Reis May 15 '14 at 01:54