2.3 Algorithms

-time complexity -space complexity

-how much time an algorithm requires to solve a particular problem -known as big-o notation, shows the effectiveness of the algorithm -shows the amount of time taken relative to the number of data elements given as an input

-constant time complexity -the amount of time taken to complete an algorithm is independent from the number of elements inputted

-linear time complexity -the amount of time taken to complete an algorithm is directly proportional to the number of elements inputted

-polynomial time complexity -the amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted

-polynomial time complexity -the amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n

-exponential time complexity -the amount of time taken to complete an algorithm will double with every additional item

-logarithmic time complexity -the time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted

-logarithmic time complexity -the time taken to complete an algorithm grows at a rate that is proportional to the number of elements inputted multiplied by the logarithm of n

log n n log n

-the amount of storage the algorithm takes -measured using big o-notation

best- 0(n) as this is when array is already sorted average- 0(n^2) as this is when elements are randomly ordered worst- 0(n^2) as this is when the elements are sorted in reverse order

0(1) as it requires additional space for number of variables

best- 0(n) as this is when array is nearly sorted average- 0(n^2) as this is when array is randomly sorted worst- 0(n^2) as this is when array is sorted in reverse order

0(1) as minimal extra space needed

all- 0(n log n) as the algorithm is being decomposed –> log n, due to the number of separations becomes n log n

0(n) as merge sort requires additional space for merging

best- 0(n log n) as this is when the pivot consistently divides array in half and is balanced average- 0(n log n) as this is when the pivot consistently divides array in half and is balanced worst- 0(n^2) as this is when the pivot consistently results in unbalanced partitions

0(log n) as there is varying space depending on pivot and data

best- 0(1) as this is when the target is at beginning of the list average- 0(n) as this is when the target can be randomly anywhere in the list, multiple iterations worst- 0(n) as this is when the target element is at the end of the list or not present

0(1) requires minimal space as nothing will be added or lost

best- 0(1) as this is when the target is at the middle of the sorted list average- 0(n log n) as each comparison reduces the search space by 1/2 worst- 0(n log n) as the target element could be at the beginning or end of the sorted list

0(1) no extra space needed

best- 0(1) when there are no collisions and the hash function distributes keys evenly average- 0(1) no collisions and a good hash function worst- 0(n) as this is when there are many collisions which leads to a linear search within the has table search