∑

UGC NET CS Formula Chart

239+ formulas across 8 subjects

⏱

Algorithm Complexity

(23 formulas)

Constant

O(1)

Does not depend on input size

Example: Array access, hash lookup

Logarithmic

O(log n)

Halves problem each step

Example: Binary search

Linear

O(n)

Proportional to input

Example: Linear search, single loop

Linearithmic

O(n log n)

n times log n

Example: Merge sort, heap sort

Quadratic

O(n²)

Nested loops

Example: Bubble sort, insertion sort

Cubic

O(n³)

Triple nested loops

Example: Floyd-Warshall, matrix multiply

Exponential

O(2ⁿ)

Doubles with each input

Example: Subset enumeration, TSP brute force

Factorial

O(n!)

All permutations

Example: Permutation generation

Master Theorem Case 1

T(n) = aT(n/b) + f(n), if f(n) = O(nˡᵒᵍ_b(a)⁻ᵉ) → T(n) = Θ(nˡᵒᵍ_b(a))

f(n) is polynomially smaller

Where: a≥1 subproblems, b>1 size reduction, f(n) combine cost

Master Theorem Case 2

if f(n) = Θ(nˡᵒᵍ_b(a)) → T(n) = Θ(nˡᵒᵍ_b(a) · log n)

f(n) is same order

Where: a≥1 subproblems, b>1 size reduction

Master Theorem Case 3

if f(n) = Ω(nˡᵒᵍ_b(a)⁺ᵉ) → T(n) = Θ(f(n))

f(n) is polynomially larger

Where: a≥1 subproblems, b>1 size reduction

Binary Search

T(n) = T(n/2) + O(1) → O(log n)

Divide by 2, constant work

Example: a=1, b=2, f(n)=1

Merge Sort

T(n) = 2T(n/2) + O(n) → O(n log n)

Two halves, linear merge

Example: a=2, b=2, f(n)=n

Strassen Matrix

T(n) = 7T(n/2) + O(n²) → O(n^2.81)

7 subproblems of half size

Example: a=7, b=2, f(n)=n²

Bubble Sort

Time: O(n²) | Space: O(1)

Best: O(n) with early exit

Where: Stable, in-place

Selection Sort

Time: O(n²) | Space: O(1)

Always O(n²), not stable

Where: In-place, not stable

Insertion Sort

Time: O(n²) | Space: O(1)

Best: O(n) for sorted input

Where: Stable, in-place, online

Merge Sort

Time: O(n log n) | Space: O(n)

Always O(n log n)

Where: Stable, not in-place

Quick Sort

Avg: O(n log n) | Worst: O(n²) | Space: O(log n)

Worst case on sorted input

Where: Not stable, in-place

Heap Sort

Time: O(n log n) | Space: O(1)

Build heap O(n) + extract O(n log n)

Where: Not stable, in-place

Counting Sort

Time: O(n+k) | Space: O(k)

k = range of values

Where: Stable, not comparison-based

Radix Sort

Time: O(d·(n+k)) | Space: O(n+k)

d = digits, k = base

Where: Stable, not comparison-based

Comparison Sort Lower Bound

Ω(n log n)

Any comparison-based sort needs at least n log n comparisons

Where: Decision tree has n! leaves, height ≥ log₂(n!)