SFWRENG 2C03 Study Guide - Midterm Guide: Universal Hashing, Liquid Oxygen, Binary Tree

• School: McMaster University
• Department: Software Engineering
• Course: SFWRENG 2C03
• Professor: R. Khedri

Document Summary

Asymptotic bounds: the behaviour of a function as functions get very large and approach infinity. Note: disregard any constants, since they become negligible as functions get very large: big omicron: o , big theta, big omega: , small o, small omega: > f n. 0: g n f n g n lim n g(n) is going to be much bigger than f(n) o(n): Page 6 of 38 for (g(n) = f(n), f n g n lim n. Page 47: given a function g(n) g n f n. Generally, we focus on the o(n) because it models how the algorithm increases. If you want to find out information about an algorithm, use the . Strictly: can only be going up or down. To figure out how long an algorithm takes, find the number of iterations. b n. , multiply both sides by n2 to get: c. O(n) is sometimes only true between a given range.