Big Everything and Proofs Flashcards
Put the following in order of size
- 2n
- n2logn
- 1
- n0.5
- nlog2n
- log(n)
- n
- n2
- n3
- nn
- 3n
- nlog(n)
- n1.5
- n!
What are the 5 different types of asymptotic notation?
Roughly speaks, f(n) E of the following means:
When building the Big-Oh definition, what is step one?
When building the Big-Oh definition, what is step two?
What is the official definition of Big-Oh? Also explain it in plain language
As we’ve learned in discrete math, the order of quantifiers matter.
Changing the definition only, what would be the format of the definition given the following to prove:
What is the rough work for the following:
What is the actual proof of the following
Provide the proof for the following
How do you prove that something is NOT big oh? What needs to be done to the definition first?
Express the statement in words as well
Show the proof for the following
What is the definitinon of Big-Omega and what is it in plain language?
In general what would a graph look like of Big-Omega?
What is the theorem for the relationship between Big-Oh and Big-Omega?
What is the official definition of Big-Theta and what does it mean in english?
What is the theorem that is equivalent to the definition of Big-Theta?
In general, how do you prove Big-Theta using the theorem?
Prove the first step
Prove the following
Do it
Prove the following
Do it
Prove the following
Do it
Prove the following
Do it
Prove the following
Do it
Prove the following
Do it
Prove the following
Do it
