U401 SAC Notes Time Complexity

Question 1

Describe binary search and its one limitation

Answer 1

Repeatedly divides the array in half until the target element is found or if the array is empty,by comparing the middle element with the target element.

One limitation is that the array must be sorted to begin with.

Question 2

Recurrence relation for Binary Search

Answer 2

T(n) = T(n/2) +O(1) where d = 0

Question 3

What is the master theorem

Answer 3

A tool that is used to solve recurrence relations in divide and conquer algorithms

Question 4

Time complexity for binary search

Answer 4

O(logn) - worst case
O(1) - best case (if the target value is the middle value)

Question 5

Time complexity for merge sort

Answer 5

O(nlogn)

Question 6

Time complexity for quick sort

Answer 6

Best case- O(nlogn)
Worst case- O(n^2)

Question 7

Recurrence relation for Merge sort

Answer 7

T(n) = 2T(n/2) + O(n^1)

Question 8

Recurrence relation for quick sort

Answer 8

best case-
T(n) = 2T(n/2) + O(n^1)
worst case
T(n) = T(n-1) + O(n)

Question 9

explain the correct structure of a recurrence relation that permits the use of the Master Theorem

Answer 9

Only recurrence relations of the form T(n) = aT(n/b) + f(n)

where a >=1
b>1
f(n)>0

Question 10

What is merge sort?

Answer 10

Merge sort is a divide and conquer algorithm as it recursively divides the array into smaller subarrays to sort then merging them back together to obtain the resultant sorted array.

Question 11

What is quick sort?

Question 12

What is recursion?

Answer 12

a method where a problem is divided into smaller, simpler problems until a condition is met. This technique involves a function calling itself to solve the sequential smaller problems.

Question 13

If the algorithm was modified to include the reading of a file of sorted data. What would be the overall big-oh
time complexity of the algorithm

Answer 13

O(N)