[Follow here] for daily coding insights.

DSA using Python

Time & Space Complexity — The Ultimate Beginner-to-Pro Guide for Engineering Students Preparing for High-LPA Placements

Understanding Time and Space Complexity is the first and most important step in Data Structures & Algorithms. Every top company — Google, Amazon, Microsoft, Infosys, TCS Digital, Zoho, Walmart, Oracle, Atlassian — evaluates how efficiently you write code.

This post gives you a crystal-clear foundation with intuition, real examples, formulas, and interview-ready questions.

1. What is Time Complexity?

Time Complexity measures how the running time of a program grows with input size (n).

-You don’t measure time in seconds.
-You measure growth rate.

Example:

A program takes 1ms for 10 elements
It may take 2ms for 20 elements
It may take 4ms for 40 elements

This is O(n) growth — proportional to input.

2. Why Time Complexity Matters?

Because in interviews, two codes may give the correct output, but:

One runs in 0.1 seconds
The other takes 40 seconds

Companies choose the developer who writes the faster algorithm.

3. The Big-O Family (Very Important)

Big-O — Worst Case

Maximum time required.

Big-Theta (Θ) — Average Case

Typical/expected time.

Big-Omega (Ω) — Best Case

Minimum time possible.

Interviewers mainly focus on:
✔ Big-O (worst case)
✔ Sometimes Θ (average)

4. Standard Big-O Complexities (Must Memorize)

From best to worst:

Complexity	Name	Example
O(1)	Constant	Accessing array element
O(log n)	Logarithmic	Binary search
O(n)	Linear	Loop through array
O(n log n)	Linearithmic	Merge sort
O(n²)	Quadratic	Nested loops
O(2ⁿ)	Exponential	Subset generation
O(n!)	Factorial	Permutations

5. Visual Intuition (Easy to Remember)

O(1): Flat line
O(log n): Slow rise
O(n): Straight diagonal
O(n²): Steep curve
O(2ⁿ): Skyrocket

6. Time Complexity Examples

Example 1: Constant Time

print(arr[5])

➡ Complexity: O(1)

Example 2: Linear Time

for i in range(n):
    print(i)

➡ Complexity: O(n)

Example 3: Quadratic Time

for i in range(n):
    for j in range(n):
        print(i, j)

➡ Complexity: O(n²)

Example 4: Logarithmic Time

binary_search(arr, key)

➡ Complexity: O(log n)

7. Space Complexity

Space Complexity measures extra memory used by your algorithm.

Two types:

Input space → Space for input
Auxiliary space → Extra memory algorithm uses

Example:

temp = []

Extra list → additional memory → O(n)

8. Why Space Complexity Is Important

Companies love candidates who write:

Faster code
Memory-efficient code

Especially in product-based companies where optimization is everything.

9. Common Space Complexity Patterns

Code Pattern	Complexity
Using a single variable	O(1)
Using arrays, lists	O(n)
Using 2D arrays	O(n²)
Recursion depth n	O(n)
Hash maps	O(n)

10. Best Case, Average Case, Worst Case (Easy Explanation)

Searching an element in an array:

Array: [5, 3, 9, 6, 8], Search: 8

Best Case (Ω(1)) → element found at index 0
Average Case (Θ(n)) → random position
Worst Case (O(n)) → last index or not found

11. Time Complexity of Common Operations

Array

Access → O(1)
Insert at end → O(1)
Insert at beginning → O(n)
Search → O(n)

Linked List

Search → O(n)
Insert at beginning → O(1)

Stack/Queue

Push/Pop/Enqueue/Dequeue → O(1)

Binary Search Tree

Search →
- Best: O(log n)
- Worst: O(n) (unbalanced tree)

12. Interview-Standard Example Problems

Q1: What is the time complexity?

for(int i=1; i<=n; i=i*2) {
    System.out.println(i);
}

Answer: O(log n)

Q2:

for i in range(n):
    for j in range(i):
        print(i, j)

➡ Complexity:
= 1 + 2 + 3 + … + n
= O(n²)

Q3: Recursion Example

def fun(n):
    if n == 0:
        return
    fun(n-1)

➡ Complexity:

Time: O(n)
Space: O(n) recursion depth

13. 20 Practice Questions (Interview-Level)

What is the complexity of accessing an element in an array?
What is the complexity of searching an element in a linked list?
Complexity of bubble sort?
Complexity of merge sort?
Complexity of binary search?
Complexity of inserting at the end of an array?
Complexity of inserting at the beginning of a linked list?
Complexity of BFS?
Complexity of DFS?
Space complexity of recursion?
Why do we analyze algorithms?
What is Big-O notation?
What is the worst-case complexity of quicksort?
What is the best-case complexity of quicksort?
What is n² in terms of Big-O?
What is log₂n in Big-O terms?
Does Big-O give exact time?
Which is faster: O(n) or O(log n)?
What is auxiliary space?
Why recursive algorithms need extra space?

Conclusion

Time & Space Complexity is the foundation of your DSA journey.
Master this, and every future topic — arrays, strings, trees, graphs, DP — becomes far easier.

ALSO CHECK

DS(Data Structure) C Edition

Time & Space Complexity

Also Other DSA Topics
Insertion Sort
Merge Sort
Bubble Sort
Selection Sort
Singly Linked List

Recursion Hacker Rank Example

Tail Recursion and Optimisation

Recusrion Tree and Complexity Analysis

Advanced Recursion : Deep Dive : Recursion Trees and the Master Theorem

DSA Series Chapter 1 Time & Space Complexity