121 Week 13 - Linear, Sentinel and Binary Search

Question 1

How are the 3 time complexities calculated

Answer 1

Best case: calculate the lower bound on the running time of an algorithm.
Worst case: calculate the upper bound on the running time of an algorithm.
Average case: take all possible inputs and calculate the computing time for all of the inputs. Sum all the calculated values and divide the sum by the total number of inputs.

Question 2

How does a linear search work

Answer 2

Goes through every item in the array until it finds the item.
If it reaches the end and the item has not been found, the item is not in the array.

Question 3

Linear search best and worst case time complexities

Answer 3

Best case: T(N) = 4, constant time complexity
Worst case: T(N) = 3n+3, linear time complexity

Question 4

How do you find average case for linear search

Answer 4

Find the average number of times all non-constant instructions are executed by finding the sum of how many times each is executed for different positions of iSearch in the array.
Divide the sum of times executed by N to find the average number of executions for each instruction.
Add up average and constant instruction execution counts to find overall average case.

Question 5

Linear search average case time complexities

Answer 5

iSearch is in the array: T(N) = 3/2N + 5/2
iSearch isn’t in the array: T(N) = 3n+3
Probability iSearch is in the array: P
Probability iSearch isn’t in the array: 1-P
Overall average case: P(3/2N + 5/2) + (1-P)(3n+3) = (3/2P+3-3P)N + 5/2P+3-3P)

Question 6

What is sentinel search

Answer 6

Sentinel search is a type of linear search that reduces the comparisons compared to a regular linear search.

Question 7

How does sentinel search work

Answer 7

1. Check last element of array. If it is the same as iSearch, then return 1 because iSearch has been found. If it is not the same as iSearch then replace the last element with iSearch.
2. Perform a linear search as normal but when iSearch is found, return the logic statement (i < (n-1) instead of 1.
   This means that if iSearch has been found then 1 is only returned if you are not at the last element in the array, as it would be the element that was replaced by iSearch in the first step.

Question 8

Sentinel vs linear search time complexities

Answer 8

Linear worst-case instruction count: 3n+3
Sentinel worst-case instruction count: 2n+3
Both have linear time complexity but sentinel search is faster than as it does not have to check if it is in range of the array when the loop restarts.

Question 9

What is binary search

Answer 9

A sorting algorithm that is more time efficient than linear and sentinel search but only works on sorted arrays.

Question 10

How does binary search work

Answer 10

1. Find the midpoint of the array using mid = (high+low/2). High and low will always be the length of the array and 0 respectively at the start of the search. If the midpoint is a decimal, then round up.
2. If the midpoint == iSearch, return 1 to show iSearch has been found. If midpoint != iSearch and low == high, return 0 as iSearch is not in the array.
3. If iSearch is less than the midpoint, set high to be the index of the midpoint.
   If iSearch is lower than the midpoint, set low to be the index of the midpoint plus 1.
4. Return to step 1.

Question 11

Binary search time complexities

Answer 11

Best case: C1, constant complexity
Worst case: C1 + C2LogN, logarithmic complexity

Question 12

What is growth of functions

Answer 12

Represents how a functions output reacts to increasing inputs size

Question 13

Growth rate of functions from fastest to slowest

Answer 13

1 → Constant growth
log n → Logarithmic growth
n^c → where 0<c<1
n → Linear growth
n log n
n2 → Quadratic growth
n^2 log n
n^3 → Cubic growth
n^c → Polynomial growth (c is a constant number)
2^n → Exponential growth
3^n → Exponential growth
c^n → Exponential growth (c is a constant number)
n! → Factorial growth