View Single Post
Mar8-12, 06:25 PM
I don't know how copies and compares are factored into complexity or big theta.
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 = (k
- k) n compares done, how do you balance the copies versus compares for O(...) in this case?