问题描述:

This is an optional question in a course I'm taking, and they provide the answer, 4n. But now matter how much I think about it I cannot figure out how they came to this. I'm still very new and just learning about big O notation so I'm sure I'm missing something simple but it doesn't make sense to me. The way I think about it is bubble sort requires n * k operations, so if you make k into 2k I have n * 2k. And I believe in worst-case scenario k = n - 1 so it's practically n * 2n AKA 3n. I'm probably doing this completely wrong, but that's why I'm here for help. My course didn't really (or I don't feel) it covered a problem like this so I'm just not sure how to approach it. Thanks!

bubble sort is Big O k^2 complexity, both worst case and average

so we have n operations for size k, which implies that k^2 = n

so we double k, we have (2k)^2 = X or 4k^2 = X where X =# of operations for 2k size

plug in the fact that n=k^2, and you have 4n=X

Theres your answer :)