Efficiency of Algorithms - Part 1 Flashcards
What do we need to do to analyze the efficiency of two algorithms?
give 2 examples
count some significant measure of what affects the performance.
- significant operations
- number of lines of code
consider the ____ when counting the number of times a line of code is executed
worst case
what defines the efficiency of the algorithm?
the function that comes from adding up all the execution count values for each line
What do we need to know to compare the efficiency of two algorithms?
whether one function is greater than another
What does it mean for one function to be greater than another?
it grows faster
Why is there no natural total ordering of functions?
they are defined on so many values
give an example of a partial ordering of functions
f is less than or equal to g if f of x is less than or equal to g of x everywhere.
what is wrong with some partial orders?
many functions aren’t comparable throughout every possible x value
What is Big-O’s advantage?
introduces 2 constants that make more functions comparable
What are the two constants of Big-O notation? describe them.
C, a multiplier, makes the constant factors matter less
n_0, a beginning point, so we only care about things happening from this point onward
How do we define the ordering of Big-O
f is less than or equal to g if Big-O of f, which is a set, is a subset of Big-O of g
What are the 3 requirements for a partial order?
- reflexive
- Antisymmetric
- Transitive
what does reflexive mean?
everything is less than or equal to itself
what does anti-symmetric mean?
if one element is less than another and vice versa, the two have to be equal
what is the transitive property?
if x is less than or equal to y and y is less than or equal to z then x has to be less than or equal to z
