We generally break complexity down into two main types:

• Time Complexity: How long does the algorithm take to run? (Measured in the number of basic operations executed, not actual seconds, since hardware speeds vary).

• Space Complexity: How much extra memory or storage does the algorithm need while it's running?

At its core, time complexity isn't about counting the exact seconds a program takes to run. It's about measuring how the running time grows as the input size grows.

Think of it this way: if it takes 1 second to search a physical phone book of 100 pages, how long does it take if the phone book grows to 1,000,000 pages? Does it take 10,000 times longer, or just a few extra seconds?

We use Big O Notation (like O(1), O(n), etc.) to group algorithms by their growth rates.

The Scale: Big O Notation

• Big O notation is a way of describing how the running time of an algorithm grows as the input size grows. It is a mathematical way of saying that the running time of an algorithm is asymptotically equal to some function of the input size.

• In simple English, Big O notation can be thought of as the worst-case running time of an algorithm. It is the upper bound on the running time of the algorithm, no matter what the input data is.

• Instead of measuring time in exact seconds (which changes depending on how fast your computer is), Big O measures how the number of operations scales. It focuses entirely on the worst-case scenario.

• O(1) — Constant

  • How it scales: Time stays exactly the same, no matter how much data you add.

  • Real-world example: Looking up an element in an array by its index.

  • Code Example:

def get_first_element(lst):

   return lst[0]  # Always takes 1 step, whether the list has 10 or 1,000,000 items

• O(log n) — Logarithmic

  • How it scales: Time increases slightly each time the data doubles. (Highly efficient).

  • Real-world example: Finding a word in a physical dictionary using Binary Search.

  • Code Example:

def binary_search(lst, target):

   low, high = 0, len(lst) - 1

   while low <= high:

       mid = (low + high) // 2  # Cutting the search space in half

       if lst[mid] == target:

           return mid

       elif lst[mid] < target:

           low = mid + 1

       else:

           high = mid - 1

   return -1

• O(n) — Linear

  • How it scales: Time grows in direct, equal proportion to the size of the data.

  • Real-world example: Reading through every page in a book from start to finish.

  • Code Example:

def print_all_elements(lst):

   for item in lst:  # Runs exactly 'n' times for a list of size 'n'

       print(item)

• O(nlogn) — Linearithmic

  • How it scales: A bit slower than linear, common in highly efficient divide-and-conquer sorting algorithms.

  • Real-world example: Sorting a deck of cards using Merge Sort or Quick Sort.

  • Code Example:

# Python's built-in Timsort (used by .sort()) runs in O(n log n) time

lst.sort()

• O(n^2) — Quadratic

  • How it scales: Time grows exponentially relative to the data. Twice the data takes four times as long.

  • Real-world example: Comparing every single item in a list to every other item (Nested Loops).

  • Code Example:

def print_all_pairs(lst):

   for item1 in lst:        # Runs n times

       for item2 in lst:    # Runs n times for every outer loop iteration

           print(f"{item1}, {item2}")

The Golden Rules of Big O

When you are analyzing code to determine its Big O complexity, keep these two foundational rules in mind:

1. Drop the Constants

Big O only cares about the long-term trend, not the exact count. If a function loops through an array twice, it technically takes 2n operations. In Big O, we drop the constant 2 and just call it O(n).

2. Drop the Less Significant Terms

If your algorithm has a part that takes O(n^2) time and another part that takes O(n) time, the O(n^2) completely dominates as n gets massive. We ignore the smaller piece. Therefore, O(n^2 + n) simplifies down to just O(n^2).

Whenever a solution to a problem is written some memory is required to complete. For any algorithm, memory may be used for the following:

• Variables (This include the constant values, temporary values)

• Program Instruction

• Execution

When you write code, it doesn't just need time to run—it also needs a physical place to live while it's working. Space complexity is the measure of how much total memory (RAM) an algorithm needs to run to completion relative to the size of the input.

Just like time complexity, we measure space complexity using Big O notation to look at the worst-case scenario as inputs grow.

The Two Parts of Space

Total space complexity is actually made up of two distinct buckets:

Total Space Complexity = Auxiliary Space + Input Space

• Input Space: The memory required to store the initial data passed into the algorithm.

• Auxiliary Space: The extra or temporary memory your algorithm allocates while solving the problem (e.g., local variables, new arrays, or call stack memory).

Note: In the real world, software engineers usually care most about Auxiliary Space. If someone asks you to optimize an algorithm's space complexity, they typically mean "stop creating so many temporary variables," since you usually can't control the size of the input coming in.

Memory Usage while Execution

• While executing, algorithm uses memory space for three reasons:

• Instruction Space

  • It's the amount of memory used to save the compiled version of instructions.

• Environmental Stack

  • Sometimes an algorithm(function) may be called inside another algorithm(function). In such a situation, the current variables are pushed onto the system stack, where they wait for further execution and then the call to the inside algorithm(function) is made.

  • For example, If a function A() calls function B() inside it, then all the variables of the function A() will get stored on the system stack temporarily, while the function B() is called and executed inside the funciton A().

• Data Space 

  • Amount of space used by the variables and constants.

• But while calculating the Space Complexity of any algorithm, we usually consider only Data Space and we neglect the Instruction Space and Environmental Stack.

Common Space Complexities

• O(1) Constant Space: The memory required by the algorithm remains constant, regardless of the input size. The algorithm only uses fixed-size variables or pointers (e.g., swapping elements using two pointers).

• O(N) Linear Space: The memory required grows linearly in proportion to the size of the input. Common when creating copies of arrays or using simple loops that scale with N.

• O(N²) Quadratic Space: The memory grows proportionally to the square of the input size, frequently seen when handling 2D arrays (matrices). 

• O(log N) Logarithmic Space: Often seen in recursive algorithms where the call stack grows logarithmically, like in balanced binary search trees.