CSI 2110 Study Guide - Binary Search Tree, Avl Tree, Binary Tree
27 Apr 2013
School
Department
Course
Professor
Document Summary
Algorithm - a step by step procedure for solving a problem in a finite amount of time. Primitive operations - low-level computations independent from the programming language that can be identified in the psuedocode. Big-oh - given two functions and , we say is if and only if there are positive constant and such that for . It means that an algorithm has the complexity of. Just multiply all terms by the highest degree of , add, and you have your (the coefficient) and (the function). Logarithms always in base 2 in this class unless otherwise stated. Always want the lowest possible bound, approximation should be as tight as possible. Drop lower order terms and constant factors. Big-omega - is such that for all . It means an algorithm has the complexity of at least . Big-theta - is if it is ( ) ( ) it means the complexity is exactly .
