CSI 2110 Chapter Notes - Chapter 4: Pseudocode, Analysis Of Algorithms
15 Sep 2017
School
Department
Course
Professor
Document Summary
4. 1. 1 the constant function f(n) = c, for some fixed constant c. Does not depend on the value of n. 4. 1. 2 the logarithm function f(n) = logbn, for some fixed constant b>1. Compute the small integer greater than or equal to logan (equal to the number of times a divides n until we get a number equals to or less than 1) The most common base is 2 (b/c of binary) Arises when we do a single operation for each element. Best algorithm to process n objects that are not already in memory. Grows a little faster than linear function, a lot slower than quadratic. 4. 1. 6 the cubic function and other polynomials f(n)=n3. 4. 1. 7 the exponential function f(n) = bn, b>0 b=2 in most algorithm analysis. Eg. loop that doubles operations performed with each iteration. Ideally operations should run in times proportional to constant or logarithm. Above table shows growth rates for all seven functions.
