CSC 225 SPRING 2021

ALGORITHMS AND DATA STRUCTURES I

ASSIGNMENT 2 - WRITTEN

UNIVERSITY OF VICTORIA

1. Count the number of assignments and comparisons (all of them) for each of the following algorithms using summation notation.

a) Algorithm Loop1():

b) Algorithm Loop2():

2. a) Consider the following recurrence equation, defining a function T(n):

Use top-down repeated substitution to derive the closed form of this equation.

b) Consider the following recurrence equation, defining a function T(n):

Show by induction that .

3. Order the following list of functions by their big-Oh notation. Group together (for example, by underlining) those functions that are big-Theta of one another. (No justification needed).

Note: unless otherwise stated.

Hint: When in doubt about two functions f() and g(), consider log f() and log g() or .

4. Prove each of the following using the definition of Big-Oh.

5. Describe a recursive method for solving ln(!). Note, you cannot use the recursive factorial algorithm presented in lecture 4. That is, your algorithm fact_ln(n) should call fact_ln(n-1). Count the assignments (including returns) and comparisons in order to derive a recurrence equation for the worst-case runtime of your algorithm.