Runtime of Insertion Sort?
Note 1: ETH::A&D
Deck: ETH::A&D
Note Type: Algorithms
GUID:
modified
Note Type: Algorithms
GUID:
LqP`8lU$&o
Before
Front
Back
Runtime of Insertion Sort?
Best Case: \(O(n)\)
Worst Case: \(O(n^2)\)
This insertion is not in constant time! We have to swap with each previous element!
After
Front
Runtime of Insertion Sort?
Back
Runtime of Insertion Sort?
Best Case: \(O(n \log n)\)
Worst Case: \(O(n^2)\)
This insertion is not in constant time! We have to swap with each previous element!
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Runtime | <div>Best Case: \(O(n)\)</div><div>Worst Case: \(O(n^2)\)</div> | <div>Best Case: \(O(n \log n)\)</div><div>Worst Case: \(O(n^2)\)</div> |