CSC 325 Practice Test Questions and Correct Answers

Big O Notation A way of expressing the worst-case run-time of an algorithm, useful for comparing the speed of two algorithms. Big Theta Notation A way to express the average case runtime of an algorithim, Big Omega Notation A way to express the lower bound of an algorithims run time Loop Invariant A statement that holds true for all iterations of an algorithim. Can be proved by induction Basic Operation The operation within a function that is done the most times. Used to find the time complexity of the algorithim Recurrence Relation A recurrance relation is an equation that expresses how a recursive algo grows, helps us determine the runtime of the algo. Substitution Method If given T(n) we solve for the inner part of the quation ex: if the equation is T(n/2) + 1 we solve for T(n/2) and plug that value into the original equation. Repeat this process until we see a pattern and see what the kth iteration would look like. Then solve for k. Mastering Method Cases Case 1: f(n) < loga base b solution is Big Theta(n ^ loga base b) Case 2: f(n) = loga base b solution is n^k logn Case3: f(n) > loga base b solution is n^k Mastering Maethod Explanations View Reccurance relation in following format T(n) = aT(n/b) + f(n) also note that f(n) = n^k Then examine the three cases and produce an answer.