intro Flashcards
(16 cards)
What is an algorithm?
A step-by-step procedure for solving a problem in a finite amount of time.
what is a Data structure?
A way for data to be organized in computer memory.
What is a program?
A program is a set of instruction which the computer will follow to solve a problem or perform a computation
What types of algorithm efficiency is measured?
- Time: execution time
Space: memory and disk usage
What is linear growth?
O(N) = algorithms solve problems very quickly
what is quadratic growth?
algorithms become impractical for inputs exceeding a few thousand
(grow very quickly)
what is cubic growth?
algorithms are impractical for input sizes exceeding a few hundred
what is big O notation?
notation for caputring asymptotic growth rate. Used to capture the most dominant term in a function that eventually will dominate all others to have the most accurate rate of growth.
Example of big o?
for T(N) = N^2 + N + 3
the big o is O(N^2)
What is big omega notation?
An optimistic estimate of the time complexity or “best fit”. Will eventually grow at least as fast as the best fit. The element of the equation with the tightest bound to the actual projected answer (think graphically)
Example of big omega?
for T(N) = N^2 + N + 3
big omega will be N^2 as it will eventually be as quick as N^2
“The slowest rate at which the function grows, for large inputs — ignoring constant and low-order noise”
Ω(N) means the function grows at least as fast as 𝑁. N^2 definitely does that!
what is a big theta notation?
If “best element” and big O is the same. Same order of growth and is bounded above and below by same value
Example of big theta?
for T(N) = N^2 + N + 3
theta(N^2) is the answer as it was both the tightest bound and the upper bound.
order by growth rate
logN<N<NlogN<N^2<2^N
thing to remember with big omega?
You can always say
Ω(anyslowerfunction)
🚫 But only the dominant term gives you a tight bound.
Any function that grows slower than the dominant term can still be used in Ω, but won’t be tight.
So
T(N)∈Ω(N^2) is the best description even though Ω(N) is also true.
rule of thumb for notation?
Omega: anything <= dominant term
O: anything >= dominant term
theta: Only dominant term
