Cheatography

DSA in Python Cheat Sheet (DRAFT) by aman-senpai

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.