DataStructures / Data structures Interview questions
How insertion sort is faster than bubble sort?
In bubble sort at i-th iteration you have n-i-1 inner iterations ((n^2)/2), but in insertion sort you have maximum i iterations on i-th step, but i/2 on average, as you can stop inner loop earlier, after you found correct position for the current element. So you have (sum from 0 to n) / 2 which is (n^2) / 4.
More Related questions...