问题描述:

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 :)

您可能感兴趣的文章：

- c# - Writing .GetValues more efficiently?
- mysql - What will happen if I changed the collation of my database?
- java - convert double[] into Number[] in android
- ubuntu - Python specific item from last line
- java - Is there a general argument about return style for a "conditional" method?
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial