Two pieces of info that let you analyse an algorithm
Time + Space complexity
What’s meant by the time complexity of algorithms
The amount of time required to solve a problem
How is time complexity measured
Using big o notation
What does the big o notation show
The effectiveness of an algorithm
What’s big o notation good for
Predicting the amount of time taken to solve an algo given the num of items stored
What’s a linear time complexity
Amount of time taken = num of elements inputted
What’s a constant time complexity
Amount of time taken to complete an algorithm is independent to the number of inputted elements
What’s a polynomial time complexity
Amount of time taken to complete an algorithm is proportional to number of items inputted to power of n
What’s an exponential time complexity mean
Amount of time taken to complete an algorithm is proportional to 2 to the power of num of items inputted
Log time complexity mean?
Time taken to complete an algorithm increases at a smaller rate as the number of elements inputted
What’s a logarithm
How many times a certain number is multiplied together to reach another number
What’s space complexity
Space complexity is the amount of storage space an algorithm takes up
What’s an algorithm
An algorithm is a sequence of instructions to complete a task
How do you reduce space complexity
Try complete all operations on same data set
How do you reduce the time complexity of an algorithm
You reduce the amount of embedded for logos and then reduce the amount of item you complete the operations on same => divide and conquer
Big o notation of linear search algotitm
O(n)
Big o notation of binary search algorithm
O(log n)
Big o notation of bubble sort algorithm
O(n^2)
