CS240 Study Guide - Midterm Guide: Pseudocode, Avl Tree, Priority Queue
Document Summary
The complexity of a loop is expressed as the sum of the complexities of each iteration of the loop. Nested loops: start with the innermost loop and proceed outwards. Use -bounds throughout the analysis and obtain a -bound for the complexity of the algorithm. Prove an o-bound and a matching -bound separately. Use upper bounds (for o-bounds) and lower bounds (for -bound) early and frequently. This corresponds to doing fix-downs on existing array. # of instances of size n is the number of input permutations. Add the runtimes of good and bad instances. Multiply the probability of a good instance by the runtime of a good instance. Find the runtimes on a if the random number is good and bad. Multiply the probability of a good random number by the sum of the running time for all instances. Running time is the good case running time from before times the probability of the random number (pr(r"))
