RUSES
Would you like to react to this message? Create an account in a few clicks or log in to continue.
May 2024
MonTueWedThuFriSatSun
  12345
6789101112
13141516171819
20212223242526
2728293031  

Calendar Calendar


Recurrence Relations and bubble sort

Go down

Recurrence Relations and bubble sort Empty Recurrence Relations and bubble sort

Post  VicVic Wed Feb 29, 2012 4:22 am

So my recurrence relation for bubble sort gives me the general time of:
T(n) = T(n-1) +n

Which is fine. That's how Anderson explained it to me so it should in theory be right.

Apparently this is equal to n^2 but when I try and prove this using induction, it fails horrendously. Any ideas?

Also there was something about (n(n-1))/2 but I'm not sure how that comes into it.

VicVic

Posts : 17
Join date : 2012-02-28

Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum