CSC3360 Analysis of Algorithms Fall 2022
HW 2 – Runtime Analysis of Algorithms
Objectives
• Be able to describe the running time of an algorithm using recursive function.
• Be able to analyze the efficiency of an algorithm using formal notation.
Key Ideas
• Recursive expression for running time.
• Insertion and merge sorts.
• Divide-and-conquer approach.
• Θ notation.
Homework Problems
Reference: Lecture notes and Chapter 2
1. (10 points) Using Figure 2.2 on the textbook as a model, illustrate the operation of
INSERTION-SORT on the array A =< 30, 41, 59, 26, 41, 20, 68 >. Show intermediate
results for each iteration. What is the running time for INSERTION-SORT with a list
of n integers in Θ notation?
2. (5 points) Express the following functions in Θ notation.
• n
3 − 100n
2 + 50n + 600
• nlg(n) + 50n + 20
• 2
4+2n + 30n
2 + 100
3. (5 points) p37. 2.3-1. What is the running time for a list of n integers in Θ notation?
4. (10 points) p39. 2.3-3
Hint: Use k as independent variable instead of n because n is an exact power of 2 and
there is no case with n+ 1 . First, verify the case for k = 1. Then, assume the formula is
true for k and use the hypotheses to prove the formula is true for k+1. Finally, conclude
the formula is true for k.
5. (5 points) What is the running time for executing the following code fragment in Θ
notation? Assume n is the size of the problem and it takes c amount of time to execute
the statement sum = sum + i * j; once.
int n;
int sum = 0;
for( int i = 0; i < n; i++)
for( int j = n; j >= 1; j = j/3)
sum = sum + i * j;
Page 2
