Q1. Write down the output, purpose and perform asymptotic analysis of the following.
int a = 0, i = N;
while (i > 0) {
a += i;
i +=3;
Algorithm ABC (n)
If(n=1)
return 1
else
return n=n*ABC(n-1)
Q2. For the functions, nk and cn,, what is the asymptotic relationship between these
functions?
Assume that k >= 1 and c> 1 are constants.
1. nk is O( cn)
2. Cn is O(nk)
Q3. Write down the output, purpose and perform asymptotic analysis of the following.
int i, j, k = 0;
for (i = n / 2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n / 2;
}
Algorithm ABC(a,b, temp)
if(temp % b == 0 && temp % a == 0)
return temp;
temp++;
ABC(a,b, temp);
return temp;
Q4. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?
1. X will always be a better choice for small inputs
2. X will always be a better choice for large inputs
3. Y will always be a better choice for small inputs
4. X will always be a better choice for all inputs
Q5. Perform asymptotic analysis of each of the following loops. The standard function min returns the
minimum of the two arguments.
A. for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < n/2; ++j ) { ++sum; }}
B. for ( int i = 0; i < n; ++i ) { for ( int j = 0; j < std::min( 10, i ); ++j ) { ++sum; }}
C. for ( int i = 0; i*i < n; ++i ) { ++sum; }
Q6. Show that the following sum is n(n + 1).
n
∑2k
k =1
Q7. For each function f(n) below, give an asymptotic upper bound using “big-Oh” notation. You should
give the tightest bound possible.
(a) f(n) = 100n3 −7n3 + 14n2
(b) f(n) = 100n3 −10n4 + 7n2
(c) f(n) = n3(1 + 6n + 2014n2)
(d) f(n) = (logn)(n + n2)
¨Q8. Code Selection sort, Insertion sort and Bubble sort.
🞑 Against each sort, I want three graphs. One for worst case, one for best case, and one for average
case.
🞑 On the x-axis should be the increasing input size (n), on the y-axis should be the running time.
🞑 To avoid the system dependencies, against each value of n, repeat 10 experiments and use the
average value.
🞑 In all, there should be 9 graphs in your document against this question.
Q9. Solve the following recursive functions using Substitution, Tree and master Method.
• T (n) = 3T (n/3)+ pn
• T (n) = 4T (n/2)+ cn
• T (n) = 3T (n/4)+ n log n
• T (n) = 3T (n/3)+ n/2
• T (n) = 6T (n/3)+ n2 log n
• T (n) = 4T (n/2)+ n/ log n
• T (n) = 64T (n/8)− n2 log n
• T (n) = 7T (n/3)+ n2
• T (n) = 4T (n/2)+ log n
• T(n)=2T(n-1)+O(n)
• T(n) =3T(n/3) + O(n)
Q10. See the Algorithms of Merge sort and Quick sort in the Book of “Introduction to Algorithms” form
there recursive function and solve them to find total time complexity.
