Asymptotic Notation
2026-11-18
notes / Algorithms-1
Algorithms-1
Hard Method
for j = 2 to A.length |
|
|
key = A[j] |
|
|
| i = j - 1 |
|
|
while i > 0 && A[i] > key |
|
|
A[i+1] = A[i] |
|
|
i = i - 1 |
|
|
A[i+1] = key |
|
|
is the number of times the while loop repeats for every value of j
Total Cost:
Then analyse
- best case
- and worst case possibilities
Finally express in the most general form you can e.g. as a quadratic you can then say is a quadratic function of
Notation
in equality and inequalities
comparing functions
- and implies
- this is true for and as well
-
- also true for and
Standard Functions
Polynomials
asymptotically positive polynomial ()
exponential
Examples
2024MA