Scribd
Upload
3 views3 pages

Tutorial 1

This document is a tutorial on Data Structures and Algorithms focusing on complexity analysis, recurrence relations, and recursion. It includes two questions: ranking functions by their order of growth and analyzing a recursive divide-and-conquer algorithm's running time. Each question has specific rubrics for grading, totaling 10 marks.

Uploaded by

panwaranushka30
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Tutorial 1

This document is a tutorial on Data Structures and Algorithms focusing on complexity analysis, recurrence relations, and recursion. It includes two questions: ranking functions by their order of growth and analyzing a recursive divide-and-conquer algorithm's running time. Each question has specific rubrics for grading, totaling 10 marks.

Uploaded by

panwaranushka30
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures and Algorithms

Tutorial 1
Complexity Analysis, Recurrence Relations, Recursion

Total Marks: 10

Question 1 [5 Marks]

Rank the following functions according to their order of growth. Partition your list into
equivalence classes such that two functions f (n) and g(n) belong to the same class if and
only if
[ f(n)=Θ(g(n)).]

Functions to Rank
n
1. lg(lg∗ n) 11. 22 21. en
∗
2. 2lg n 12. n1/ lg n 22. 4lg n
√
3. ( 2)lg n 13. ln ln n 23. (n + 1)!
√
4. n2 14. lg∗ n 24. lg n
5. n! 15. n2n 25. lg∗ (lg n)
√
6. (lg n)! 16. nlg lg n 26. 2 2 lg n

n
7. 32 17. ln n 27. n
8. n3 18. 1 28. 2n
9. (lg n)2 19. 2lg n 29. n lg n
10. lg(n!) 20. (lg n)lg n 30. 22n+1

Rubric: See Assessment Rubric (Page 3).

Question 2 [5 Marks]

Consider a recursive divide-and-conquer algorithm whose running time is given by


[ T(n)=3T n4 + n2 .]


Using the recursion-tree method, answer the following:

(a) Draw the recursion tree for the given recurrence.

1
(b) Determine the cost at each level of the recursion tree.

(c) Find the total cost of the recursion tree.

(d) Determine the asymptotic running time using Θ-notation.

Rubric: See Assessment Rubric (Page 3).

End of Tutorial

2
Assessment Rubric

Question 1 Rubric
Ordering of Functions 3 Marks
Correct ranking of functions according to asymptotic growth rates.

Equivalence Classes 2 Marks


Correct grouping of functions using Θ-notation.

Total 5 Marks

Question 2 Rubric
Recursion Tree Construction 2 Marks
Correct construction and representation of the recursion tree.

Level-wise Cost Analysis 1 Mark


Correct determination of the cost at each level.

Total Cost and Complexity Analysis 2 Marks


Correct derivation of total cost and asymptotic complexity.

Total 5 Marks

Overall Marks: 10

You might also like