View Single Post
Mar8-12, 05:25 PM
HW Helper
P: 7,183
Quote Quote by rcgldr View Post
I don't know how copies and compares are factored into complexity or big theta.
Quote Quote by Max.Planck View Post
It doesn't matter, we don't care about constants in asymptotic notation.
OK, but in one type of optimized case, there are k n copies done and in the worst case, (k) (k-1) n = (k2 - k) n compares done, how do you balance the copies versus compares for O(...) in this case?