A community for students.
Here's the question you clicked on:
 0 viewing
s3a
 4 years ago
(Bubble sort complexity Question)
Here is the problem:
http://f.imgtmp.com/APYz8.jpg
.
For part (a), I'm really unsure as to how I should proceed.
As for (b), I need help in figuring out how the primitive operation estimations are conducted.
As for (c), I would think it is O(n^2) since the nested for loops would run n*n = n^2 times if the inner for loop did not have a i in the "to n  1  i" part. So, I'm guessing it's something like O( n^2*log(n) ) but I'm just making an educated guess and have not taken any real objective steps.
Any help would be GREATLY appreciated!
Thanks
s3a
 4 years ago
(Bubble sort complexity Question) Here is the problem: http://f.imgtmp.com/APYz8.jpg . For part (a), I'm really unsure as to how I should proceed. As for (b), I need help in figuring out how the primitive operation estimations are conducted. As for (c), I would think it is O(n^2) since the nested for loops would run n*n = n^2 times if the inner for loop did not have a i in the "to n  1  i" part. So, I'm guessing it's something like O( n^2*log(n) ) but I'm just making an educated guess and have not taken any real objective steps. Any help would be GREATLY appreciated! Thanks

This Question is Closed

anonymous
 4 years ago
Best ResponseYou've already chosen the best response.0a) The input that would cause the worse running time would be an array that is sorted in descending order. Reason: every loop it would have to do a swap. b) In the worst case you would have to do assign i = 0 arithmetic n  1 condition i != n  1 for (i = 0; i < n  1; i++) { assign j = 0 arithmetic n  1  i condition j != n  1  i for (j = 0; j < n  1  i; j++) { arithmetic j + 1 access A[j + 1] access A[j] condition A[j + 1] < A[j] if (A[j + 1] < A[j]) { access A[j] assign tmp = A[j] arithmetic j + 1 access A[j + 1] assign A[j] = A[j + 1] assign A[j + 1] = tmp tmp = A[j] A[j] = A[j + 1] A[j + 1] = tmp } arithmetic j++ arithmetic n  1  i condition j < n  1  i } arithmetic i++ arithmetic n  1 condition i < n  1 } I'm using E for the summation operator (capital sigma) and to simplify this a little i'll assume array access starts at 1 T(n) = 3 + E(i=1 to n) (6 + (ni+1)(13) ) T(n) = 3 + 6*n + 13*E(i=1 to n) ( (ni+1) ) Do you know of arithmetic progressions? If not there is at least one you need to know for computer science E(i=1 to n) (i) 1 + 2 + 3 + ... + n = n*(n+1)/2 eg 1 + 2 + 3 = 6 3*(3+1)/2 = 3*4/2 = 6 so (ni+1)(13) will be done n times in terms of the number of operations E(i=1 to n) (i) = E(i=1 to n)(ni+1) i ni+1 ________________ 1 n 2 n1 3 n2 . . . . n  2 3 n  1 2 n 1 See how the sum of both sides are equal T(n) = 3 + 6*n + 13*E(i=1 to n) (i) T(n) = 3 + 6*n + 13*n*(n+1)/2 c) bigOh of T(n) is O(n^2) Hope this clears up any troubles you've been having =)

s3a
 4 years ago
Best ResponseYou've already chosen the best response.0Thanks for the detailed answer! I have a question though: is i != n  1, for example, actually 1 primitive operation or is it 2 primitive operations since n  1 is a primitive operation and then it's actually checking if that is not equal to i.
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.