Ch2 ppt Fundamentals of Analysis of Algorithm Efficiency Flashcards
The time required by the algorithm
Time efficiency/ complexity
The time required by the algorithm
space efficiency/complexity
Analyzing the running time efficiency of algorithms
What to analyze?
The size of the input is the main consideration for analyzing the
running time,
Count the number of times each of the algorithm’s operations (of
loops/recursions) is executed
The running time of algorithms can be different. Best case of the
running time is of little interest, average case is difficult to
calculate (not apparent what constitutes an “average” input for a
problem, worst case representing the running time, that is, the
longest running time for any input size, n.
The eight most important functions, f(n), used in the
analysis of algorithms
– The Constant Function (1)
– The Logarithm2
Function (log2n)
– The Linear Function (n)
– The N-Log2
-N Function (nlog2n)
– The Quadratic Function (n2)
– The Cubic Function and Other Polynomials (n3)
– The Exponential Functions (2n)
– The Factorial Functions (n!)
the constant function
f(n) = c for some fixed constant c where n is the input
size.
The logarithm function
f(n) = log2n = x if and only if 2
x = n where 2 is the
base and n represents the input size.
– By definition, log{2}1 = 0
the linear function
f(n) = log2n = x if and only if 2
x = n where 2 is the
base and n represents the input size.
– By definition, log21 = 0
the N-log{2}-N function
f(n) = n log2 n where n is the input size.
The quadratic function
f(n) = n^2 where n is the input size.
the cubic function and other polynomials
f(n) = n^3 where n is the input size.
the exponential function
f(n) = 2^n, 3^n , …, or n^n where n represents the
input size.
factorial function
f(n) = n! where n represents the input size.
Notations used to describe the
running time of algorithms
asymptotic notation
O-notation (upper bound)
Let f(n) and g(n) be functions that f(n) is bounded above
by some constant multiple of g(n)
Omega notation (lower bound)
Let f(n) and g(n) be functions that f(n) is bounded
below by some constant multiple of g(n)
theta notation (average bound)
Let f(n) and g(n) be functions that f(n) is bounded both
above and below by some constant multiple of g(n)
General plan for analyzing the time-efficiency of
nonrecursive algorithms
– Determine the input size, n
– Identify the algorithm’s loops
– Count the number of times the loops is executed using
frequency count method depending on the worst-case or
best-case efficiency
– Sep up a sum expressing the number of times the
algorithm’s loops is executed
– Find its order of growth
many algorithms are recursive in nature.
A ____ _____ is used to describe the overall running
time of recursive algorithms on inputs of sizes.
recurrence relation
in ____ _____, to sort a given array, we divide it in two
halves and recursively repeat the process for the two halves. Finally
we merge the results. The recurrence relation of the running time of
Merge Sort can be written as T(n) = 2T(n/2) + cn.
Merge Sort
Plan for analyzing the time-efficiency of recursive algorithms
– Determine the input size, n
– Identify the algorithm’s recursions
– Count the number of times the recursions is executed
depending on the worst-case or best-case efficiency
– Sep up a recurrence relation expressing the number of
times the algorithm’s recursions is executed
– Solve the recurrence
recursive algorithm substitution method:
Forward substitution method
we solve the recurrence relation
for n = 0, 1, 2, … until we see a pattern. Then we make a
guesswork, predict the running time, and verify the guesswork is
correct by using the induction.
recursive algorithm substitution method:
Backward substitution method
we solve the recurrence relation
for n = n, n-1, n-2, … or n = n, n/2, n/4, … until we see a pattern.
Then we make a guesswork, predict the running time, and verify
the guesswork is correct by using the induction.
forward substitution method
Compute the factorial function f(n) = n! for an arbitrary
nonnegative integer n >= 1.
Draw a recurrence tree and
calculate the time taken by every level of tree. Finally, sum
the work done at all levels. To draw the recurrence tree,
start from the given recurrence and keep drawing till find a
pattern among levels. The pattern is typically a arithmetic
or geometric series
recurrence tree method
steps to solve the recurrence
relation using recursion tree method.
– Create a recursion tree from the recurrence relation
– Calculate the work done in each node of the tree
– Calculate the work done in each level of the tree (this can
be done by adding the work done in each node
corresponding to that level).
– The sum over the work done in each level to get the
solution.
The running time is equal to the running time
of the two recursive calls plus the linear time
spent in the partition.
T(N) = T(i) + T(N-i-1) + cN
where T(0) = T(1) = 0 and
i = the number of elements in one partition
Quick-sort
