1. Big O
1.1 Big O
•
Big O is a notation used to describe the computational complexity of an algorithm
•
There are 2 types of computational complexity we have to consider : time complexity & space complexity
◦
Time complexity : amount of time the algorithm needs to run relative to the input size
→ How much longer does the algorithm take to complete as the input size grows?
◦
Space complexity : amount of memory allocated by the algorithm when running relative to the input size
→ How much more memory does the algorithm use as the input size grows?
◦
Time complexity is considered more important than space complexity
1.2 How complexity works
•
a math formula describes complexity, is often used to denote the length of an input array or string.
→
→ is used to denote any nother arbitrary variables
•
time complexity describes how the number of operations changes as the input change
Calculating Time Complexity
1.
ignore constants
→ as the input size increases, the number of operation required increase linearly
→ O(9999999n) = O(8n) = O(n)
2.
consider the complexity as the variables tend to infinity
→ , plays the most crucial role when
3.
Best complexity possible is , constant time/ constant space
→ algorithm always used the same amount of resources, regardless of the input
→ it doesn’t mean algorithm is fast, it means that its runtime is independent of the input size
Logarithmic time
•
logarithm is the inverse operation to exponents
•
logarithmic time complexity means the input is being reduced by a percentatge at every step
→ Binary search algorithm runs in , at first step, we consider the entire input , and at second step, we only consider elements, after second step, we consider elements and so on. As we reduce our search space by 1/2, we can run in logarthmic time complexity.
