What is O(n) and O(log n)? | Learn Time & Space Complexity

O(log n) vs O(n) – Time and Space Complexity Explained

Understanding Time & Space Complexity: O(n) vs O(log n)

If you’re learning data structures and algorithms, you’ll often hear about terms like O(n) and O(log n). These are used to describe how fast (or slow) an algorithm runs and how much memory it uses. Let’s break it down in a simple way so even beginners can understand.

📌 What is Time Complexity?

Time complexity tells us how the execution time of an algorithm increases as the input size increases. It helps us compare the efficiency of different algorithms.

Think of it like this: If you double the size of your input, how much longer does the algorithm take?

📌 What is Space Complexity?

Space complexity is the amount of memory an algorithm uses while running. It includes both the input data and any extra memory used (like temporary variables, stacks, etc.).

🚀 O(n) — Linear Time

O(n) means the algorithm runs in direct proportion to the input size.

Example: Printing all elements in a list of size n. 
for i in range(n):
    print(arr[i])
  • If n = 10 → 10 steps
  • If n = 1000 → 1000 steps

This is called **linear time** — more data means more time linearly.

🧠 Space Complexity for O(n)

If the algorithm stores a copy of the array or another structure that depends on input size, it may also use O(n) space.

Example: Making a copy of a list. 
new_list = arr.copy()

⚡ O(log n) — Logarithmic Time

O(log n) means the algorithm cuts down the work in half at every step. This is very efficient.

Example: Binary Search. 
def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
  • If n = 1000 → Only ~10 steps
  • If n = 1,000,000 → Only ~20 steps
📉 O(log n) algorithms are very fast, especially for large data.

🧠 Space Complexity for O(log n)

Usually constant (O(1)) unless recursion is used, then the call stack may take O(log n) space.

🆚 Comparison Table

Aspect O(n) O(log n)
Type Linear Logarithmic
Speed Slower for large inputs Faster for large inputs
Example Algorithm Linear Search Binary Search
Use Case Go through each element Divide and conquer

🎓 When to Use Which?

  • O(n) is common and simple. Use it when you need to process or visit every element.
  • O(log n) is more advanced and efficient, especially for sorted data or tree-based structures.

✅ Key Takeaways

  • O(n): Grows with input size — simple, but can be slow for large data.
  • O(log n): Super fast — cuts data in half each time.
  • Know the structure of your data to choose the right algorithm.

Start analyzing your code with time and space in mind — it will help you in coding interviews, internships, and real-world development!