Efficiency of Algorithms - Part 2 Flashcards
What do data structure courses actually mean when they say Big-O?
Big-Ø
Big-Omega is essentially the ____ of Big-O
opposite
big-omega defines a ___ ___
partial order
What is the difference in the definitions of Big -O and Big-Omega?
where we had f of n less than or equal to g of n before, we now have f of n greater than or equal to g of n.
T/F: Big-Theta is defined using both Big-O and Big-Omega
True
Big-Theta is the ____ of Big-Omega and Big-O
intersection
Why isn’t Big-O unique?
it is just an ordering
Rather than ___ ___ Big-Theta defines an ___ ___
partial order
equivalence relation
What does an equivalence relation mean?
when some function f is in Big-Theta of g, both functions grow at the same rate
When do we say that f and g are equivalent?
When Big-Theta of f is equal to Big-Theta of g
T/F: n and 2n are equal according to Big-Theta.
True
T/F: n and n2 are equal according to Big-Theta
False. not equal
Big-Theta groups functions into ____ ____
equivalence classes
What do all members of an equivalence class have in common?
They grow at the same rate
list the axioms required for a relation to be an equivalence relation
reflexive
Symmetric
Transitive
define the Symmetric axiom
when x is equal to y y is equal to x
What do equivalence relations do to sets?
partition them into equivalence classes
list 2 equivalence relations
modulo 4
equality of fractions
What resources are we interested in measuring the efficiency of?
CPU time
Memory
what technique did we use to figure out CPU time?
counting lines of code
T/F: In many cases, the memory requirements are constant.
True
One of which two program features need to be present for the memory requirements to be more than constant?
dynamic allocation of memory
recursion
Why does recursion need more memory?
It uses increasing amounts of the compiler’s run-time stack as the depth of recursion increases
How can we determine the complexity of a problem?
considering the most efficient known algorithms for solving a particular problem
What are intractable problems?
problems for which all known algorithms require more than polynomial time. the are amount the most difficult solvable problems.
