Searching, Sorting, and Complexity Analysis Flashcards
Things to desire in a program
Correctness, Robustness, Maintainability, Efficiency
Two ways to measure efficiency
Empirical and Analytical
What is empirical measurement?
Using a clock to get actual running times for different inputs
Empirical problems
Different machines have different running times
Some running times are so long that it is impractical to check them
What is analytical measurement?
Using pencil and paper to determine the abstract amount of work that a program does for different inputs
Analytical advantages
Machine independent
Can predict running times of programs that are impractical to run
What is complexity analysis?
Pick an instruction that will run most often in the code
Determine the number of times this instruction will be executed as a function of the size of the input data
Focus on abstract units of work, not actual running time
Searching for the minimum
Most often instruction: assignment (=)
For a list of length n, n assignments: O(n)
What is Big-O notation?
Big-O notation expresses the amount of work a program does as a function of the size of the input
What does O(N) stand for?
O(N) stands for order of magnitude N, or order of N for short
Common orders of magnitude
Constant: O(k)
Logarithmic: O(log2(n))
Linear: O(n)
Quadratic: O(n^2)
Exponential: O(k^n)
Examples of approximation
N + K goes to N
N/K and N*K go to N
Use the highest degree term in a polynomial and drop the others: (N^2 - N)/2 goes to N^2
Sequential search vs. Binary search
O(n) vs. O(log2(n))
Selection sort
Withing minInRange, a loop runs n - i times
minInRange runs n times
(n^2 - n)/2 goes to O(n^2)
Regular fib(n)
fib(n) = 1, when n = 1 or n = 2 fib(n) = fib(n -1) + fib(n - 2) otherwise
Somewhere between 1^n and 2^n
