Scribd
Upload
30 views2 pages

Time Complexity Cheat Sheet

This document provides a cheat sheet for time complexities, detailing loop complexities, recursive functions, and common patterns. It includes examples such as O(n), O(n^2), and O(log n) along with general tips for analyzing time complexity. A reference table categorizes various time complexities for quick reference.

Uploaded by

523163
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
30 views2 pages

Time Complexity Cheat Sheet

This document provides a cheat sheet for time complexities, detailing loop complexities, recursive functions, and common patterns. It includes examples such as O(n), O(n^2), and O(log n) along with general tips for analyzing time complexity. A reference table categorizes various time complexities for quick reference.

Uploaded by

523163
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
You are on page 1/ 2

Time Complexity Cheat Sheet

1. Loop Time Complexities:


---------------------------
for i in range(n): --> O(n)
for i in range(n):
for j in range(n): --> O(n^2)
for i in range(n):
for j in range(i): --> O(n^2) (Triangular loop)
for i in range(0, n, 2): --> O(n) (step size > 1)
while n > 1:
n = n // 2 --> O(log n)

2. Recursive Functions:
------------------------
Fibonacci (naive): --> O(2^n)
Binary Recursion (divide 2): --> O(log n)
Merge Sort / Quick Sort: --> O(n log n)

3. Common Patterns:
--------------------
Binary Search: --> O(log n)
Binary Search in loop: --> O(n log n)
Constant time operations: --> O(1)

4. General Tips:
-----------------
- Ignore constants: O(3n + 2) = O(n)
- Highest order term matters: O(n^2 + n) = O(n^2)
- Recursion depth * work per level = total time
5. Reference Table:
--------------------
O(1) --> Constant Time
O(log n) --> Logarithmic Time
O(n) --> Linear Time
O(n log n) --> Linearithmic Time
O(n^2) --> Quadratic Time
O(2^n) --> Exponential Time

You might also like