Show Menu
Cheatography
  1. Home >
  2. Programming >

DSA in Python Cheat Sheet (DRAFT) by

This is for coding interview.

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Complexity Analysis (Time/­Space)

Complexity
Notation
Descri­ption
O(1)
Constant
Time/Space complexity remains constant regardless of input.
O(log n)
Logari­thmic
Time/Space complexity grows logari­thm­ically with the input.
O(n)
Linear
Time/Space complexity grows linearly with the input.
O(n log n)
Linear­ithmic
Time/Space complexity grows linearly multiplied by log n.
O(n^2)
Quadratic
Time/Space complexity grows quadra­tically with the input.
O(n^3)
Cubic
Time/Space complexity grows cubically with the input.
O(2^n)
Expone­ntial
Time/Space complexity grows expone­ntially with the input.
O(n!)
Factorial
Time/Space complexity grows factor­ially with the input.
Big O Notation
Big O notation is used to analyze the efficiency of algorithms and represent their upper-­bound time comple­xity. It helps us understand how the algori­thm's perfor­mance scales with the input size.
  

Best, Average, and Worst Case Complexity

Case
Descri­ption
Best Case
The minimum time complexity under optimal input.
Average Case
The expected time complexity for random input.
Worst Case
The maximum time complexity for any input.
To determine the complexity of an algorithm, follow these steps:

1. Identify the major operations in the algorithm.
2. Analyze how many times each operation is executed concerning the input size.
3. Eliminate lower-­order terms and constants to find the dominant term.
Choose the approp­riate complexity notation from the Big O table.