Ch2 ppt Fundamentals of Analysis of Algorithm Efficiency

Question 1

The time required by the algorithm

Answer 1

Time efficiency/ complexity

Question 1

The time required by the algorithm

Answer 1

space efficiency/complexity

Question 2

Analyzing the running time efficiency of algorithms
What to analyze?

Answer 2

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.

Question 3

The eight most important functions, f(n), used in the
analysis of algorithms

Answer 3

– 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!)

Question 4

the constant function

Answer 4

f(n) = c for some fixed constant c where n is the input
size.

Question 5

The logarithm function

Answer 5

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

Question 6

the linear function

Answer 6

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

Question 7

the N-log{2}-N function

Answer 7

f(n) = n log2 n where n is the input size.

Question 8

The quadratic function

Answer 8

f(n) = n^2 where n is the input size.

Question 9

the cubic function and other polynomials

Answer 9

f(n) = n^3 where n is the input size.

Question 10

the exponential function

Answer 10

f(n) = 2^n, 3^n , …, or n^n where n represents the
input size.

Question 11

factorial function

Answer 11

f(n) = n! where n represents the input size.

Question 12

Notations used to describe the
running time of algorithms

Answer 12

asymptotic notation

Question 13

O-notation (upper bound)

Answer 13

Let f(n) and g(n) be functions that f(n) is bounded above
by some constant multiple of g(n)

Question 14

Omega notation (lower bound)

Answer 14

Let f(n) and g(n) be functions that f(n) is bounded
below by some constant multiple of g(n)

Question 15

theta notation (average bound)

Answer 15

Let f(n) and g(n) be functions that f(n) is bounded both
above and below by some constant multiple of g(n)

Question 16

General plan for analyzing the time-efficiency of
nonrecursive algorithms

Answer 16

– 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

Question 17

many algorithms are recursive in nature.
A ____ _____ is used to describe the overall running
time of recursive algorithms on inputs of sizes.

Answer 17

recurrence relation

Question 18

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.

Answer 18

Merge Sort

Question 19

Plan for analyzing the time-efficiency of recursive algorithms

Answer 19

– 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

Question 20

recursive algorithm substitution method:
Forward substitution method

Answer 20

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.

Question 21

recursive algorithm substitution method:
Backward substitution method

Answer 21

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.

Question 22

forward substitution method

Answer 22

Compute the factorial function f(n) = n! for an arbitrary
nonnegative integer n >= 1.

Question 23

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

Answer 23

recurrence tree method

Question 24

steps to solve the recurrence
relation using recursion tree method.

Answer 24

– 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.

Question 25

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

Answer 25

Quick-sort