lectures.alex.balgavy.eu

Lecture notes from university.
git clone git://git.alex.balgavy.eu/lectures.alex.balgavy.eu.git
Log | Files | Refs | Submodules

Shit I don_t remember but should (midterm edition).md (1072B)

      1 +++
      2 title = "Shit I don't remember but should (midterm edition)"
      3 +++
      4 
      5 # Shit I don't remember but should (midterm edition)
      6 
      7 Worst-case complexities:
      8 
      9 - O(n^2)
     10     - Bubblesort
     11     - Insertion sort
     12     - Quicksort — but very rare, average O(nlogn)
     13 - O(nlogn)
     14     - Mergesort
     15     - Heapsort
     16 - O(n+k) — k is range, n is number of elements
     17     - Counting sort
     18     - Bucket sort
     19 - O(n)
     20     - Radix sort: O(d(n+k)), where d is dimension (number of digits)
     21 
     22 Calculating recurrence equations:
     23 1. Find T(n) in terms of i, base is i = 1 (not 0!!!)
     24 2. Find n for T(n) to be 1
     25 3. Calculate i in terms of n when T(n) is 1
     26 4. Substitute i in T(n) and simplify
     27 
     28 Priority queue can be done with max heap
     29 
     30 Correctness
     31 
     32 - Loop invariant, show:
     33     - Initialisation: true prior to first iteration
     34     - Maintenance: if true before iteration, remains true after iteration
     35     - Termination: when loop terminates, invariant gives useful property that helps show the algorithm is correct
     36 
     37 Summations:
     38 
     39 - ![](1f1c4ec570db9d8d636503b88c239f60.png)
     40 - ![](85fc1da988814d4954ddabc21f3851b6.png)