CH 2 Fundamentals of Algorithm Analysis Flashcards
What is an algorithms basic operation and why is it important?
The basic operation is the operation that contributes most to the total running time. (usually the most time consuming operation in the algorithms inner most loop).
What is the established framework for the analysis of an algorithms time efficiency?
Time efficiency is analyzed by determining the number of repetitions of the algorithms basic operation as a function of input size.
T(n) = kC(n) where k is the execution time for the basic operation, C(n) is the number of of times the basic operation is executed as a function of input size, and T(n) is the running time of the algorithm.
Big-O Definition
f(n) is upper bounded by g(n) if and only if there exists positive constants c and n_0 such that f(n) <= c(g(n)) for all n >=n_0.
Big-Omega Definition
f(n) is lower bounded by g(n) if there exists positive constants c and n_0 such that f(n) >= c(g(n)) for all n>= n_0.
Big-Theta Definition
f(n) is tightly bounded by g(n) if there exists positive constants c1, c2 and n0, s.t. c1g(n) <= f(n) <= c2(g(n)) for all n >=n0.
How to establish order of growth using limits?
Take the limit as n tends to infinity of f(n)/g(n).
- If the limit is zero, g(n) is rising faster than f(n), thus f(n) is O(g(n))
- If the limit is a positive constant, the, f(n) and g(n) have the same order of growth.
- If the limit is infinity, then f(n) is rising faster than g(n), thus f(n) is Big-Omega(g(n)).
(remember if the limit is indeterminate, we use L’Hospitals rule, tale the (derivative of numerator and denominator) then solve.)
Solve the constant summation:
n
∑c
i=1
= c+ c+ …. + c (n times) = c * n
Solve the arithmetic series:
n
∑i
i=1
.
= (n(n-1))/ 2
- write the sum forward, then backward, then add them up pairwise.
S = 1 + 2+…+(n-1) + n
S = n + (n-1) +…+2 + 1
2S = n(n-1)
S = (n(n-1))/2
