Week 2: Recursive Algorithm Time Complexity

Question 1

What are activation records?

Answer 1

Question 2

What information is stored when a new activation record is created?

Answer 2

Question 3

What params are stored in the execution stack when the main function calls BinarySearch(L, x, 0, n-1)?

Answer 3

Question 4

What are stored in each execution stack for each recursive call for the following binary search function?

Answer 4

Question 5

What method is used to solve the time complexity of recursive algorithms?

Answer 5

Question 6

What two cases are needed to compute the time complexity of binary search?

Answer 6

Question 7

What is the base case for the following algorithm? Why?

Answer 7

Question 8

Examine the following:

Question 9

What is the amount of elements examined in the first recursive call made by the binary search algorithm?

Answer 9

Question 10

What are the base case and recursive case for binary search in terms of time complexity?

Answer 10

Question 11

What equation do you use to represent recursive algorithm time complexities?

Answer 11

Recurrence equation:

Base case + recursive case

Question 12

What method do you use to solve recurrence equations for recursive time complexities?

Answer 12

Repeated substitution

Question 13

Examine the following representations for linear search and bvinary search:

Question 14

Examine and understand the repeated substitution method for binary search

Answer 14

Question 15

Example of comparing orders:

Answer 15

Question 16

Another example of comparing orders

Answer 16

Question 17

Examine the following complexity classes:

Answer 17