1
$\begingroup$

I have a very hard time understanding this proof:

$$T(N) = T(N-1)+cN$$

$$T(N-1) = T(N-2)+c(N-1)$$

$$T(N-2) = T(N-3)+c(N-2)$$

$$\vdots$$

$$T(2) = T(1)+c(2)$$

$$T(N) = T(1)+c\sum_{i = 2}^{N} i = O\big(N^2\big)$$

I can see that we have $T(N-1)$ and then $T(N-2)$ and so forth because the array to check shrinks by one each time. The $cN$ is what exactly? Why does it get decremented by one, two etc.? And how does the summation equal $n^2$ at the end, it doesn't make any sense to me. I see nowhere that $n$ is getting multiplied by itself sinse it results in $n^2$.

$\endgroup$
1
  • $\begingroup$ It takes linear time $O(N)$ to compare every elements with pivot point. $\endgroup$
    – didgogns
    Nov 9 '18 at 11:49
1
$\begingroup$

the $ck$ is the additional complexity you get by adding another element you need to sort. For example, as soon as you "sorted" 1 object, you just need to add the complexity for $N-1$, hence $T(k)=T(k-1) + ck$ where c is some constant. the $k$ on the righthand side comes from sorting the $k$'th additional input, which has complexity $k$, (since it needs to be shuffled all through the sequence in the worst case).

Hence you arrive on the bottom formula including the sum $\sum_{i=1}^N ci$. This is, by the formula for arithmetic series: $$\sum_{i=1}^N ci= cN(N+1)/2=cN^2/2 + cN/2$$ hence we get as complexity $O(N^2)$.

$\endgroup$
4
  • $\begingroup$ But why do we decrement k then c(k -1) and so on? Isn't the T(n-1) what tells us the size of the array? And how can $cN^2 /2 + cN /2$ make $n^2$? $10^2 / 2$ does not make $10^2$? $\endgroup$
    – user504783
    Nov 9 '18 at 11:58
  • $\begingroup$ and what is $T(N-1)$? it is $T(n-2)+c(n-1)$, and since you do not know $T(n-1)$, you just keep going until you know $T(n-i)$, which happens latest at $T(1)=0$, which then allows you to give a closed formula. if you have problems with such arguments, i recommend you revise induction! $\endgroup$
    – Enkidu
    Nov 9 '18 at 12:01
  • $\begingroup$ you really need to revisit $O$ notation! I never said it is the same! i said it has the same order! please be sure you know your definitions before you ask a question, that is really frustrating, I feel like somebody asks me why people drink water without even knowing what water is! $\endgroup$
    – Enkidu
    Nov 9 '18 at 12:21
  • $\begingroup$ I was just asking how it happened, no need to get mad. Don't be here if you get so frustrated. $\endgroup$
    – user504783
    Nov 10 '18 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy