What is the running time for a list of n integers in Θ notation?

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.

• n3 − 100n2 + 50n + 600

• nlg(n) + 50n + 20

• 24+2n + 30n2 + 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;