Calculating the complexity of an algorithm
It is also important to understand how to read algorithmic code and identify its complexity in terms of Big O notation. By analyzing the complexity of an algorithm, we can identify potential bottlenecks and focus on improving that specific area.
To determine the cost of a code in terms of time complexity, we need to review it step by step, and focus on the following points:
- Basic operations such as assignments, bits and math operations, which will usually have constant time (O(1)).
- Logarithmic algorithms (O(log (n))) typically follow a divide-and-conquer strategy. They break the problem into smaller subproblems and solve them recursively.
- Loops: the number of times a loop runs directly impacts time complexity. Nested loops multiply their effects. So, if we have one loop iterating through the input of size n, it will be linear time (O(n)), two nested loops (O(nˆ2)), and so on.
- Recursions: recursive functions call themselves, potentially...
