1. What is Complexity Analysis?

Complexity Analysis is the process of evaluating how efficient an algorithm is in terms of:

• Time Complexity → How long it takes to run
• Space Complexity → How much memory it uses

It helps compare algorithms and choose the most efficient one.

2. Time Complexity

Definition

Time Complexity measures the amount of time an algorithm takes to execute as a function of the input size ( n ).

Why Time Complexity Matters

• Predicts performance for large inputs
• Helps optimize programs
• Essential for scalable systems

Common Time Complexities

Examples

Constant Time — O(1)

x = arr[0]

• Takes same time regardless of input size

Linear Time — O(n)

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

• Time increases linearly with input

Quadratic Time — O(n²)

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

• Nested loops → slower growth

Types of Time Complexity

1. Best Case

• Minimum time required
• Example: Searching first element

2. Worst Case

• Maximum time required
• Example: Searching last element

3. Average Case

• Expected time for random input

3. Asymptotic Notations

Used to describe growth rate:

1. Big-O (O) → Upper Bound

• Represents worst-case
• Example: O(n²)

2. Big-Theta (Θ) → Exact Bound

• Tight bound

3. Big-Omega (Ω) → Lower Bound

• Best-case

4. Space Complexity

Definition

Space Complexity measures the total memory required by an algorithm as a function of input size.

Components of Space Complexity

1. Fixed Part

• Variables, constants
• Independent of input

2. Variable Part

• Depends on input size
• Arrays, recursion stack

Examples

Constant Space — O(1)

a = 10
b = 20

Linear Space — O(n)

arr = [0] * n

Recursive Space

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

• Uses stack → O(n)

5. Time vs Space Trade-Off

Sometimes:

• Faster algorithms use more memory
• Memory-efficient algorithms take more time

Example:

• Merge Sort → Faster but uses extra space
• Bubble Sort → Slower but uses less space

6. Key Observations

• Ignore constants: O(2n) → O(n)

• Focus on dominant term: O(n² + n) → O(n²)

7. Growth Comparison (Important for Exams)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

8. Final Insight

• Time Complexity → Speed of algorithm
• Space Complexity → Memory usage
• Best algorithms balance both

Short Exam Answer

Time Complexity: The time required by an algorithm as a function of input size. Space Complexity: The memory required by an algorithm as a function of input size.

Summary

Understanding time and space complexity is essential for:

• Writing efficient code
• Solving competitive programming problems
• Cracking technical interviews