Why is bubble sort O(n^2)?

by

You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the second n – 1, the third n – 2, etc., since the ith iteration of the top-level loop has the inner loop doing n - i work.

Alternatively, you could count up the work done by multiplying the amount of work done by the inner loop times the total number of times that loop runs. The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n2).

You’re making an error by trying to combine these two strategies. It’s true that the outer loop does n work the first time, then n – 1, then n – 2, etc. However, you don’t multiply this work by n to to get the total. That would count each iteration n times. Instead, you can just sum them together.

Hope this helps!

More Related Contents:

  1. What is a plain English explanation of “Big O” notation?
  2. Big O, how do you calculate/approximate it?
  3. Constant Amortized Time
  4. Is log(n!) = Θ(n·log(n))?
  5. How can building a heap be O(n) time complexity?
  6. What’s the fastest algorithm for sorting a linked list?
  7. What would cause an algorithm to have O(log log n) complexity?
  8. What is Constant Amortized Time?
  9. Sorting in linear time? [closed]
  10. What is a bubble sort good for? [closed]
  11. Quicksort superiority over Heap Sort
  12. Why do we ignore co-efficients in Big O notation?
  13. Time Complexity of two for loops [duplicate]
  14. Prove that binary heap build max comparsion is (2N-2)
  15. What should be the algorithm of the below statement?
  16. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  17. Big-O for Eight Year Olds? [duplicate]
  18. Merge Sort a Linked List
  19. How to find the lowest common ancestor of two nodes in any binary tree?
  20. Compute the minimal number of swaps to order a sequence
  21. Computing set intersection in linear time?
  22. Programmatically obtaining Big-O efficiency of code
  23. What is the best way to get the minimum or maximum value from an Array of numbers?
  24. Sorting in place
  25. Big O when adding together different routines
  26. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  27. Comparison-based ranking algorithm
  28. how to determine if the kth largest element of the heap is greater than x
  29. Do iterative and recursive versions of an algorithm have the same time complexity?
  30. Find the k largest elements in order

Leave a Comment