Algorithmic Complexity and Big O Notation - ibrahimrifats/Back-End-development GitHub Wiki

Algorithmic Complexity and Big O Notation

When it comes to improving code efficiency, two crucial factors to consider are time and space. Time complexity refers to how long it takes for the code to run, while space complexity relates to how much memory it consumes. Big O notation is a way to measure an algorithm's efficiency in terms of time and space complexity.

Let's explore the different kinds of time complexities and how they impact the performance of algorithms:

  1. Constant Time (O(1)): Algorithms with constant time complexity will always run in the same time and space, regardless of the input size. For instance, consider a dictionary where getting the value of an item requires the key. Since the key serves as a direct pointer to the value, no iterations are needed to find it, making it constant time.

  2. Linear Time (O(n)): Algorithms with linear time complexity have a running time that grows linearly with the input size. As an example, if we have an array of numbers with a range of 100, it will run quite fast. However, if the array size is increased to a million, it will take significantly longer to complete the task. The size of the input directly affects the running time.

  3. Logarithmic Time (O(log n)): Logarithmic time complexity means that the running time grows logarithmically concerning the number of operations and the size of the input. A classic example of this is using binary search to find a target value within a sorted list. Binary search quickly narrows down the search space by dividing it in half at each step, resulting in a significantly faster search.

  4. Quadratic Time (O(n^2)): Quadratic time complexity refers to a linear operation for each value of the input data squared. Nested loops are a common cause of quadratic time complexity. For instance, if you have an outer loop that iterates 10 times and an inner loop that also iterates 10 times for each iteration of the outer loop, the total number of iterations will be 10 times 10, which is 100.

  5. Exponential Time (O(2^n)): Exponential time complexity occurs when the running time doubles with each iteration. An example of this is the Fibonacci sequence, where calculating larger Fibonacci numbers becomes increasingly time-consuming.

Understanding algorithmic complexity and how to calculate it is essential for optimizing code. By being aware of constant, linear, logarithmic, quadratic, and exponential time complexities, you are one step closer to becoming an efficient developer. Through refactoring and optimizing your code, you can tackle more significant challenges and deliver high-quality solutions that meet business requirements.