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