2.3 Algorithms Flashcards
What are two things needed to be kept into mind when developing an algorithm?
-time complexity
-space complexity
Explain time complexities? What are they known as?
-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
What is 0(1)?
-constant time complexity
-the amount of time taken to complete an algorithm is independent from the number of elements inputted
What is 0(n)?
-linear time complexity
-the amount of time taken to complete an algorithm is directly proportional to the number of elements inputted
What is 0(n^2)?
-polynomial time complexity
-the amount of time taken to complete an algorithm is directly proportional to the square of the elements inputted
What is 0(n^n)?
-polynomial time complexity
-the amount of time taken to complete an algorithm is directly proportional to the elements inputted to the power of n
What is 0(2^n)?
-exponential time complexity
-the amount of time taken to complete an algorithm will double with every additional item
What is 0(log n)?
-logarithmic time complexity
-the time taken to complete an algorithm will increase at a smaller rate as the number of elements inputted
What is 0(n log n)?
-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
What time complexity should be used for algorithms using a ‘divide and conquer approach’?
log n
n log n
What do we mean by space complexities? How can this be measured?
-the amount of storage the algorithm takes
-measured using big o-notation
What are the best/average/worst cases for time complexities for bubble sort? Why?
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
What is the space complexity for bubble sort? Why?
0(1)
as it requires additional space for number of variables
What are the best/average/worst cases for time complexities for insertion sort? Why?
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
What is the space complexity for insertion sort? Why?
0(1)
as minimal extra space needed
What are the best/average/worst cases for time complexities for merge sort? Why?
all- 0(n log n)
as the algorithm is being decomposed
–> log n, due to the number of separations becomes n log n
What is the space complexity for merge sort? Why?
0(n)
as merge sort requires additional space for merging
What are the best/average/worst cases for time complexities for quick sort? Why?
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
What is the space complexity for quick sort? Why?
0(log n)
as there is varying space depending on pivot and data
What are the best/average/worst cases for time complexities for linear search? Why?
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
What is the time complexity for linear search? Why?
0(1)
requires minimal space as nothing will be added or lost
What are the best/average/worst cases for time complexities for binary search? Why?
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
What is the space complexity for binary search? Why?
0(1)
no extra space needed
What are the best/average/worst cases for time complexities for hash table search? Why?
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
What is the time complexity for a hash table search? Why?
0(n)
as additional space is required for the storage of collisions or key-value pairs
What are the four sorting algorithms?
-bubble
-insertion
-merge
-quick
Describe bubble sort
a sorting algorithm that repeatedly loops through the list comparing elements and swapping if they’re in the wrong order
passes through the list until sorted
How does bubble sort work?
start from beginning of array
2. compare each pair of adjacent elements
3. if the elements are in the wrong order, swap them
4. repeat this process for each pair of adjacent elements in the array
5. after the first pass (passing through the whole array), repeat the whole process until a pass is made with no swaps
When may using bubble sort be inefficient?
when there are large data sets
Describe insertion sort
a sorting algorithm which places elements into a sorted sequence one element at a time
How does insertion sort work?
- start with second element of the array
- compare the element with the one before it
- if the previous element is greater, swap them
- repeat this process until element is in its correct sorted position
- move to next unsorted element and repeat steps 2-4 until the entire array is sorted
What is insertion sort useful for?
-efficient for small datasets
-good for nearly sorted data
Describe merge sort
-a divide and conquer sorting algorithm
divides the unsorted list into ‘n’ sub-lists containing one element, then uses recursion repeatedly merging sub-lists to produce sorted sub-lists until the whole array is recombined
How does merge sort work?
uses two functions: MergeSort and Merge
mergesort- divides
merge- combines
- divide the unsorted array until each element is by itself
- repeatedly merge each element ordering each element with every merge until list is fully combined
What is merge sort useful for?
efficient for large data sets
Describe quick sort
-a divide and conquer sorting algorithm
-works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according whether they are less than or greater than the pivot
How does quick sort work?
- choose a pivot element from the array
- partition the array into two sub arrays: elements less than the pivot and the other greater
- process repeated recursively on each new sub array until all elements in the input are old pivots or form a list of 1 element
What is quick sort useful for?
-efficient for large datasets
-pivot selection strategy influences performance
What are the two searching algorithms?
-binary
-linear
Describe binary search
an efficient sorting algorithm used to find the position of a target value within a sorted array or list
How does binary search work?
only works on sorted data
- find the middle element
- compare elements on either side, unwanted half is discarded
- repeat process until desired element is found or if it doesn’t exist in data set
Describe linear search
a searching algorithm which examines each element in a list or array one by one until the target value is found or the entire list is traversed
How does linear search work?
- start from the first element in list
- compare current element with target value, if successful return the index, if not, repeat with next element
- repeat step two until target is found or the end of list is reached
What is Dijkstra’s algorithm?
finds the shortest path between two nodes in a weighted graph
What is A* algorithm?
a path-finding algorithm which adds on a heuristic value to improve efficiency of the process
