Apply this limit property to the following pairs of functionsN and N2 N2 + 3N + 2 and N2 N + sin(N) and N log N and N N log N and N2 Na and Nn aN and bN (a < b) logaN and logbN (a < b) N! and NN Q9
CSSE 220 Day 27
Analysis of Algorithms intro
Bring sets of shuffled cards (index cards numbered 1-30) for teams of 3 students to sort. Bring printed schedule of classes for search example. Bring index cards for Mini-Project intro. ‹#›
What is “goodness”? How to measure efficiency? Profiling, Big-Oh Big-Oh: Motivation Informal examples Informal definition Formal definition Mathematical Application: examples Best, worst, average case
Program “goodness”
Correct – meets specifications Easy to understand Easy to modify Easy to write Runs fast Uses reasonable set of resources Time Space (main memory) Hard-drive space Peripherals …
What makes a program “good”
What kinds of things should we measure? CPU time memory used disk transfers network bandwidth Mostly in this course, we focus on the first two, and especially on CPU time One way to measure CPU time: profiling Run the program in a variety of situations / inputs Call System.currentTimeMillis() What are the problems with profiling?
Measuring program effciency
Results from profiling depend on: Power of machine you use CPU, RAM, etc State of machine you use What else is running? How much RAM is available? … What inputs do you choose to run? Size of input Specific input
Big-Oh motivation: why profiling is not enough
Big-Oh is a mathematical definition that allows us to: Determine how fast a program is (in big-Oh terms) Share results with others in terms that are universally understood Features of big-Oh Allows paper-and-pencil analysis Is much easier / faster than profiling Is a function of the size of the input Focuses our attention on big inputs Is machine independent
Big-Oh motivation: what it provides
Familiar example: Linear search of a sorted array of Comparable items
for (int i=0; i < a.length; i++) { if ( a[i].compareTo(soughtItem) > 0 ) return NOT_FOUND; // Explain why this is NOT cohesive. // NOT_FOUND must be …? else if ( a[i].compareTo(soughtItem) == 0 ) return i; } return NOT_FOUND; What should we count? Best case, worst case, average case? Q5
Does the following method actually create and return a copy of the string s? public static String stringCopy(String s) { String result = ""; for (int i=0; i
What can we say about the running time of the method? (where N is the length of the string s) What should we count? Another algorithm analysis example How can we do the copy more efficiently? Don’t be too quick to make assumptions when analyzing an algorithm! Q6
Almost everything is animated, except the initial question and the code. ‹#›
Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. --Martin Golding
We only really care what happens when N (the size of a problem) gets large Is the function basically linear, quadratic, etc. ? For example, when n is large, the difference between n2 and n2 – 3 is negligible
Run-time of the algorithm of interest on a worst-case input of size n is: at most a constant times blah, for large n Example: run-time of the linear search algorithm on a worst-case input of size n is: O(n) Alternatives to: Run-time: space required, … Algorithm of interest: Problem of interest Worst-case input: Average-case, best-case At most: At least => Ω and “exactly” (i.e. one constant for at least and another for at most) => Θ
Informal definition of big-Oh As applied to run-time analysis
≥ In this course, we won't be so formal . We'll just say that f(N) is O(g(N) means that f(n) is eventually smaller than a constant times g(n). Q7 there exists a c such that for all n >= n0
≥
f(N) is O(g(N)) if there is a constant c such that for sufficiently large N, f(N) ≤ cg(N) Informally, as N gets large the growth rate of f is bounded above by the growth rate of g f(N) is Ω(g(N)) if there is a constant c such that for sufficiently large N, f(N) ≥ cg(N) Informally, as N gets large the growth rate of f is bounded below by the growth rate of g f(N) is Θ(g(N)) if f(N) is O(g(n)) and f(N) is Ω(g(N)) Informally, as N gets large the growth rate of f is the same as the growth rate of g
Recap: O, Ω, Θ
Limits and asymptotics
consider the limit What does it say about asymptotics if this limit is zero, nonzero, infinite? We could say that knowing the limit is a sufficient but not necessary condition for recognizing big-oh relationships. It will be all we need for all examples in this course. Q8
Apply this limit property to the following pairs of functions
N and N2 N2 + 3N + 2 and N2 N + sin(N) and N log N and N N log N and N2 Na and Nn aN and bN (a < b) logaN and logbN (a < b) N! and NN Q9
D0 a few here, and suggest that they do the rest for homework ‹#›
Big-Oh Style
Give tightest bound you can Saying that 3N+2 is O(N3) is true, but not as useful as saying it’s O(N) [What about Θ(N3) ?] Simplify: You could say: 3n+2 is O(5n-3log(n) + 17) and it would be technically correct… It would also be poor taste … and put me in a bad mood. But… if I ask “true or false: 3n+2 is O(n3)”, what’s the answer? True! There may be “trick” questions like this on assignments and exams. But they aren’t really tricks, just following the big-Oh definition!
Comments