Insertion Sort:
- Best Case:
- Sorted (12345)
- O(n)
- Worst Case:
- Reverse Order (54321)
- O(n^2)
Lab 1 Qs:
1. Selection Sort
1 k=1,min = 0
2 for i=1 to A.length
3 min = A[ i ]
4 for j= i+1 to A.length
5 if min>A[ j ]
6 min = A[ j ]
7 k=j
8 if A[ i ] > min
9 swap (A[i], A[k])
Best: n^2
Worst: n
Insertion Sort Algorithm (ISA)
- Compare,then swap
Selection Sort Algorithm (SSA)
2. Prove contradiction
- A ‘tight’ asymptotic bound
- If f(n) is theta of g(n): there exists positive constants c1, c2, and n0 such that
for all - “if f(n) is theta of g(n), then the value f(n) is always between c1 * g(n) and c2 * g(n) for large values of n (n ≥ n0).”
My attempt:
Actual: