 Quote by rcgldr
I don't know how copies and compares are factored into complexity or big theta.
|
Quote by Max.Planck
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
2 - k) n compares done, how do you balance the copies versus compares for O(...) in this case?