Algorithmic Efficiency

Question 1

Bubble Sort efficiency

Answer 1

O(n2)

• -(worse case)
• -must do n operations on n items
• -quadratic increase

each iteration guarantees that an additional element on the right will be sorted
–this means you can not check last 1 after 1st sort, last 2 after 2nd sort, etc

make sure to stop sorting if the list is already sorted
–if no swaps are made on a pass