wk3/lect/notes.txt


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22


SORT
    Order (Upper Bound)
        O(n^2): Selection, Bubble
        O(n log n): Merge
        O(n):

    Omega (Lower Bound)
        Q(n^2): Selection
        O(n log n): Merge
        Q(n): Bubble

SEARCH
    Order (Upper Bound)
        O(n): Linear
        O(log n): Binary
        O(c):

    Omega (Lower Bound)
        Q(n):
        Q(log n):
        Q(1): Linear, Binary