Time complexity and Space complexity

Time Complexity

Time complexity describes how the number of operations grows as the input size N increases.

It measures how much time an algorithm takes, independent of hardware or programming language.

We focus on the number of operations, not exact timings.

To express it, we use Big-O notation, which reflects the most significant term in the function T(n) — the one that dominates as n grows.

 

 

Common Time Complexities:

 

• O(1): constant time
• O(log n): logarithmic time
• O(n): linear time
• O(n log n): linearithmic time (e.g., efficient sorting)
• O(n^2): quadratic time
• O(2^n): exponential time
• O(n!): *factorial time

*Factorial

The factorial of a natural number n is the product of all natural numbers from 1 to n

 

Why does this matter?

 

Time complexity helps us write more efficient code.

For example, improving an O(n^2) algorithm to O(n) can reduce execution from 9 seconds to 3 seconds for large inputs.

 

 

How to determine time complexity

• If a single loop iterates over a collection of n elements → O(n)
• If it iterates over half or more of the collection → O(n / 2) which simplifies to O(n)
• If you have two separate loops iterating over two different collections → O(n + m) which is still linear in total
• If you have two nested loops iterating over a single collection → O(n²)
• If you have two nested loops iterating over two different collections → O(n × m) — often written as O(n²) when both collections are of size n
• If you use a sorting algorithm on a collection → O(n log n) (common for efficient comparison-based sorts like Merge Sort or Quick Sort)

 

Space Complexity

Space complexity refers to the amount of memory (space) an algorithm uses while running.

It includes:

• Memory for variables
• Memory used by recursion
• Memory allocated dynamically during execution

In modern systems, memory has become cheaper and more abundant, so space complexity is usually less critical than time complexity — but still important in some cases.