Recurrence Relations and bubble sort
Page 1 of 1
Recurrence Relations and bubble sort
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.
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
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum