COP 3530 - Quiz #1
Big-oh notation (upper bound) - correct answer ✔- Symbol: O
g(n) <= c * f(n) for all n >= n0
Omega notation (lower bound) - correct answer ✔-Symbol : Ω
0 <= c * f(n) <= g(n) for all n >= n0
Theta notation (tight bound) - correct answer ✔-Symbol: Θ
0 <= c1 * f(n) <= g(n) <= c2 * f(n) for all n >= n0
Little-Oh Notation - correct answer ✔-Symbol: o
0 <= g(n) < c * f(n) for all n >= n0
Little omega Notation - correct answer ✔-Symbol: ω
0 <= c * f(n) < g(n) for all n >= n0
Asymptotic notation uses - correct answer ✔-simplify expressions
-O(1) denotes a constant function
- express running times of algorithms
n∑i (i=0) - correct answer ✔n(n+1)/2 = O(n^2)
n∑i^2 (i=0) - correct answer ✔n(n+1)(2n+1)/6 = O(n^3)
n∑i^3 (i=0) - correct answer ✔[n(n+1)/2]^2 = O(n^4)
, growth rate functions from slowest to fastest - correct answer ✔1, √n, n,
nlogn, nlog^2n, n^2, n^2logn, n^3, 2^n, n!
Algorithm - correct answer ✔intuitive concept: finite collection of steps to
solve a problem in a mechanical way.
formal concept: a model of a computer is defined and an algorithm is simply a
program for that ideal computer.
computability - correct answer ✔existence of algorithms
complexity - correct answer ✔algorithms consuming the least amount of
resources(time, space..)
memory - correct answer ✔each unit is able to store a primitive type value
(integer, real, character..)
Operations - correct answer ✔1. =
2. Arithmetic/math operators (+, -, *, /, %)
3. if- else
4. loops (for, while, do-while)
5.header, call, return
6. i/o statements( FileReader, BufferedReader..)
7. array atomic operations
time/cost of one operation - correct answer ✔1 unit
Big-oh notation (upper bound) - correct answer ✔- Symbol: O
g(n) <= c * f(n) for all n >= n0
Omega notation (lower bound) - correct answer ✔-Symbol : Ω
0 <= c * f(n) <= g(n) for all n >= n0
Theta notation (tight bound) - correct answer ✔-Symbol: Θ
0 <= c1 * f(n) <= g(n) <= c2 * f(n) for all n >= n0
Little-Oh Notation - correct answer ✔-Symbol: o
0 <= g(n) < c * f(n) for all n >= n0
Little omega Notation - correct answer ✔-Symbol: ω
0 <= c * f(n) < g(n) for all n >= n0
Asymptotic notation uses - correct answer ✔-simplify expressions
-O(1) denotes a constant function
- express running times of algorithms
n∑i (i=0) - correct answer ✔n(n+1)/2 = O(n^2)
n∑i^2 (i=0) - correct answer ✔n(n+1)(2n+1)/6 = O(n^3)
n∑i^3 (i=0) - correct answer ✔[n(n+1)/2]^2 = O(n^4)
, growth rate functions from slowest to fastest - correct answer ✔1, √n, n,
nlogn, nlog^2n, n^2, n^2logn, n^3, 2^n, n!
Algorithm - correct answer ✔intuitive concept: finite collection of steps to
solve a problem in a mechanical way.
formal concept: a model of a computer is defined and an algorithm is simply a
program for that ideal computer.
computability - correct answer ✔existence of algorithms
complexity - correct answer ✔algorithms consuming the least amount of
resources(time, space..)
memory - correct answer ✔each unit is able to store a primitive type value
(integer, real, character..)
Operations - correct answer ✔1. =
2. Arithmetic/math operators (+, -, *, /, %)
3. if- else
4. loops (for, while, do-while)
5.header, call, return
6. i/o statements( FileReader, BufferedReader..)
7. array atomic operations
time/cost of one operation - correct answer ✔1 unit
