121 Week 9 - Time Complexity and Searching

Question 1

Storage and retrieval speeds

Answer 1

Generally:
If storage is fast, retrieval will be slow
If storage is slow, retrieval will be fast

Question 2

Theoretical time complexity

Answer 2

The relationship between size of the input and the time taken for the algorithm to run.

Question 3

Big O

Answer 3

States the upper bound on time required for an input size.
It is the worst case scenario.

Question 4

Big O classes

Answer 4

n = size of input
O(1) –constant time (time not affected by n)
O(log n) –logarithmic time (better than linear)
O(n) –linear time (time proportional to n)
O(n log n) –(worse than linear)
O(n²) –quadratic time (time proportional to n² - slow)
O(n³) –cubic time (time proportional to n³ – very slow)
O(2n) –exponential time (very very slow)

Question 5

Linear search

Answer 5

Goes through each item from start to finish and checks if it is the desired item. If it gets to the end of the data and has not found a match, the desired item is not present.
Works on sorted and unsorted data.
Complexity O(n)

Question 6

Binary search

Answer 6

Finds the midpoint of the data and compares this to the desired item.
If desired item < midpoint, do a binary search on data less than the midpoint.
If desired item > midpoint, do a binary search on data greater than the midpoint.
If desired item = midpoint, found.
If doing binary search on a list of length 1 and desired item ≠ item, desired item is not present.
Only works on sorted data
Complexity O(log n)