A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 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

  • This Question is Closed
  1. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    a) 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 + (n-i+1)(13) ) T(n) = 3 + 6*n + 13*E(i=1 to n) ( (n-i+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 (n-i+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)(n-i+1) i n-i+1 ________________ 1 n 2 n-1 3 n-2 . . . . 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) big-Oh of T(n) is O(n^2) Hope this clears up any troubles you've been having =)

  2. s3a
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Thanks 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.

  3. anonymous
    • 4 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    i would say two

  4. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

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
  • 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.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.