Wk 1 Asymptotic Notation + Divide/Conquer Flashcards
How should each algorithm be described?
What is the analogy?
What is the diagram / visual depiction?
What is the example / experience?
What is the plain English explanation?
What is the technical description/pseudo-code?
What is the complexity? Worst-case, Best-case, Avg Case?
How is a problem like a language? How does an algorithm relate in this analogy?
Every problem is like a language, and with each instance of something we ask whether it fits in my language via the rules of the language. If it does not, we ask, how to I make it so that it would be part of my language?
What is the fastest a search problem can be accomplished? Why?
lg n. Because it takes that much space to store the parts, and to report the answer.
When do we consider an algorithm a good algorithm?
When it’s a polynomial function of n (for instance n, lg n)
Can a problem itself define an upper bound and or lower bound?
yes, for example large primes will be exponential to solved.
What is the worst case of insertion sort? Why?
n^2
What is the important question to ask when wondering if a problem can be solved faster?
How much information do I learn on each operation of the algorithm
How do lower terms in complexity formulas go away as problem size grows?
You take the limit of the complexity as n approaches infinity and lower terms grow slower than higher terms.
What three things can you say about functions, just like numbers?
….corresponds to big O, etc.
Explain in words what big O notation means.
Big O notation means that a function is upper bounded by that function. In other words, there exists constants c and n0 such that for all n greater than n0, cg(n) is greater than or equal to f(n).
What is the difference between Big O and small o of n?
Big O, there exists a constant, and an n0 (“for at least one”). For small o, for every constant, there will be a breakpoint where g(n) > f(n). (“strictly less than”)
Explain in words what small O notation means.
The function is a strict upper bounds. In other words, for every constant, there will be a break point such that cg(n) is strictly greater than f(n).
How does the limit as n approaches infinity of the ratio of f(n) / g(n) change for Big O, small O, big Omega, and small Omega?
O = k or 0 o = o Theta = k w = infinity W = k or infinity.
Explain in words Theta notation.
There exists two constants and a breakpoint such that for all n’s bigger than the breakpoint, the first constant times g(n) is greater than f(n) and the second constant times g(n) is less than f(n). It is upper and lower bounded by copies of g with different constants.
How does W, w relate to O, o?
They are the inverse. Same definitions, but different sides of the inequality sign
