Scribd
Upload
8 views7 pages

Complete Time Complexity Notes

Time Complexity measures the increase in an algorithm's running time relative to input size, represented using Big-O notation. Common time complexities include O(1), O(n), O(n^2), and O(2^n), with growth rates ordered from fastest to slowest. In interviews, the focus is typically on analyzing the worst-case scenario of an algorithm's performance.

Uploaded by

himubullapur02
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views7 pages

Complete Time Complexity Notes

Time Complexity measures the increase in an algorithm's running time relative to input size, represented using Big-O notation. Common time complexities include O(1), O(n), O(n^2), and O(2^n), with growth rates ordered from fastest to slowest. In interviews, the focus is typically on analyzing the worst-case scenario of an algorithm's performance.

Uploaded by

himubullapur02
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Complete Time Complexity Notes (Placement

Ready)

1. What is Time Complexity?

Time Complexity measures how the running time of an algorithm increases


as the input size (n) increases.

It does NOT measure actual time in seconds.


It measures number of operations performed.

We represent time complexity using Big-O notation.


2. Big-O Notation

Big-O represents the worst-case growth rate of an algorithm.

Rules:
• Ignore constants → O(2n) = O(n)
• Ignore lower order terms → O(n^2 + n) = O(n^2)
• Keep highest growing term

Example:
5n^2 + 3n + 10 → O(n^2)
3. Common Time Complexities

O(1) - Constant Time


O(log n) - Logarithmic
O(n) - Linear
O(n log n)- Linearithmic
O(n^2) - Quadratic
O(n^3) - Cubic
O(2^n) - Exponential
O(n!) - Factorial

Growth Order (Fast → Slow):


O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
4. Examples with Code Patterns

# O(1)
print(arr[0])

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

# O(n^2)
for i in range(n):
for j in range(n):
print(i, j)

# O(log n) - Binary Search


while low <= high:
mid = (low + high) // 2

# O(n log n) - Merge Sort / Quick Sort


5. Special Cases

1) Consecutive Loops:
for i in range(n):
pass
for j in range(n):
pass
Time = O(n + n) = O(n)

2) Nested Loops:
for i in range(n):
for j in range(n):
pass
Time = O(n^2)

3) Different Variables:
for i in range(n):
for j in range(m):
pass
Time = O(n * m)
6. Real Interview Examples

3Sum (Brute Force) → O(n^3)


3Sum (Two Pointer) → O(n^2)
Group Anagrams (Sorting) → O(n * k log k)
Baseball Game → O(n)

If n = 10^5:
O(n) and O(n log n) are acceptable.
O(n^2) will likely cause TLE.
7. Best, Average, Worst Case

Best Case - Minimum time taken


Average Case - Expected time
Worst Case - Maximum time taken

In interviews, we usually analyze Worst Case (Big-O).

You might also like