CSE 331 Lecture Notes - Lecture 11: Asymptotic Analysis, Binary Logarithm, Cartesian Coordinate System
Sequential Search
• Locates a target value in an array/list by examining each element from start to finish
• Linear complexity O(N)
• Best case, target at front
• Worst case, target at the end
Binary Search
• Locates a target value in a sorted array/list by successively eliminating half of the array
from consideration
• Best case, target right in the middle
• Worst case, target is at the front or end
• Log complexity O(Log(N)):
1st iteration- N/2 elements remain
2nd iteration - N/4 elements remain
Kth iteration- N/(2^K) elements remain
Done when N/(2^K) = 1-- only one thing left to look at
N/2K =1
N = 2K
Log2 N = K
Asymptotic Analysis
• Analysis of how runtime of algorithm grows as data set grows
• bigO is the upper bound of an algorithm’s asymptotic runtime
• Approximations:
o Basic operations take “constant” time
▪ Assigning a variable, accessing a field or array index
o Consecutive statements
▪ Some of time for each statement
o Function calls
▪ Time of function’s body or method
o Conditionals
▪ Time of condition + max time of branch code
o Loops
▪ Number of iterations x time for loop body
• Work your way from the inside out
Comparing Functions
• When you plot functions on a graph, those with the same complexity (4n vs n) look pretty
much the same when you zoom far out.
o If comparing the two against quadratic, then the linear looks very different
• Quadratic doesn’t start off dominating the linear, but it will eventually
o We can find the value of n when one function dominates another
• Function domination: a function f(n) is dominated by g(n) when there exists two
constants c >0 and g>0 such that for all values n>=g , f(n)<= c * g(n)
Document Summary
Sequential search: locates a target value in an array/list by examining each element from start to finish, linear complexity o(n, best case, target at front, worst case, target at the end. Binary search: locates a target value in a sorted array/list by successively eliminating half of the array from consideration, best case, target right in the middle, worst case, target is at the front or end, log complexity o(log(n)): Done when n/(2^k) = 1-- only one thing left to look at. Comparing functions: when you plot functions on a graph, those with the same complexity (4n vs n) look pretty much the same when you zoom far out. For (int j = 0; j
