Big O notation

Big O notation

https://www.bigocheatsheet.com/

Big O Basic Concepts

O(1): Constant Time

1. Doesn’t depend on the size of the data set.
2. Example: Accessing an array element by its index.

O(log n): Logarithmic Time

1. Splits the data in each step (divide and conquer).
2. Example: Binary search.

O(n): Linear Time

1. Directly proportional to the data set size.
2. Example: Looping through an array.

O(n log n): Linearithmic Time

1. Splits and sorts or searches data.
2. Example: Merge sort, quick sort.

O(n2): Polynomial Time

1. Nested loops for each power of n.
2. Example: Bubble sort (O(n2)).

Omega (Ω) – Best Case

1. What it means: Omega (Ω) describes the best-case scenario for an algorithm.
2. In simple terms: It tells you the fastest an algorithm can run in the best circumstances.

Theta (Θ) - Average Case

1. In simple terms: It tells you what to generally expect in terms of time complexity.

Big O (O) - Worst Case

1. What it means: Big O (O) describes the worst-case scenario for an algorithm.
2. In simple terms: It tells you the slowest an algorithm can run in the worst circumstances.

Drop Constants

1. O(2n) simplifies to O(n).

Drop Non-Dominant Terms

1. In O(n^2 + n), focus on O(n^2) as it will dominate for large n.