GATE CS Formula Sheet for Quick Revision

GATE CS important formulas on one page: algorithms, data structures, OS, networks, COA, digital logic, DBMS, discrete maths and probability, with solved checks.

This page collects the formulas that GATE CS numerical questions use most, subject by subject. Use it for last-month revision; each section links to the full lesson.

Algorithms and data structures

Formula	Meaning
T(n) = aT(n/b) + Θ(n^k)	Master theorem: compare a with b^k. a < b^k → Θ(n^k); a = b^k → Θ(n^k log n); a > b^k → Θ(n^(log_b a))
Binary tree with n nodes	n − 1 edges; n₀ = n₂ + 1 (leaves = nodes with two children + 1)
Height-h binary tree	At most 2^(h+1) − 1 nodes (root at height 0)
Heap of n elements	Height ⌊log₂ n⌋; build-heap is O(n)
Number of BSTs with n keys	Catalan number C(2n, n)/(n + 1)
Hashing with load factor α	Chaining: expected search ≈ 1 + α; open addressing unsuccessful search ≤ 1/(1 − α)
Simple graph with n vertices	At most n(n − 1)/2 edges; a tree has n − 1 edges

See Complexity, Recursion and recurrences and Binary trees.

Operating systems

Formula	Meaning
Turnaround time = completion − arrival	Waiting time = turnaround − burst
EAT (paging with TLB) = h(t + m) + (1 − h)(t + 2m)	h = TLB hit ratio, t = TLB time, m = memory time (single-level table)
EAT (page faults) = (1 − p)m + p × fault service time	p = page-fault rate
Page table size = (number of pages) × (entry size)	Number of pages = 2^(virtual address bits) / page size
Deadlock-free with n processes each needing k units	Resources ≥ n(k − 1) + 1

See CPU scheduling, Paging and Deadlocks.

Computer networks

Formula	Meaning
Transmission time = L / B	Propagation time = d / v
Stop-and-wait efficiency = 1 / (1 + 2a)	a = propagation time / transmission time
Sliding window efficiency = min(1, W / (1 + 2a))	W = window size
Go-Back-N: W ≤ 2^k − 1; Selective Repeat: W ≤ 2^(k−1)	k = sequence number bits
/n prefix	2^(32−n) addresses, 2^(32−n) − 2 usable hosts
CSMA/CD minimum frame	L ≥ 2 × B × propagation delay

See Flow control and IP addressing.

Computer organization

Formula	Meaning
CPU time = IC × CPI × clock period	Speedup = old time / new time
Pipeline of k stages, n instructions	(k + n − 1) cycles; ideal speedup → k
Average access time = h × c + (1 − h) × (c + m)	Cache with hit ratio h (hierarchical access)
Direct-mapped address	tag + index (log₂ lines) + offset (log₂ block size)
k-way set associative	sets = lines / k; index = log₂ sets

See Pipelining and Cache memory.

Digital logic and number systems

n-bit 2's complement range: −2^(n−1) to 2^(n−1) − 1.
A function of n variables: 2^(2^n) Boolean functions; 2^n minterms.
A mod-N counter needs ⌈log₂ N⌉ flip-flops.
IEEE 754 single precision: 1 sign, 8 exponent (bias 127), 23 mantissa bits.

See Signed numbers and Floating point.

Databases

A relation with n attributes has 2^n − 1 non-empty attribute sets, each a possible super key.
B+ tree of order p (pointers per node): a node other than the root has at least ⌈p/2⌉ children.
The natural join of R (r tuples) and S (s tuples) has at most r × s tuples.
Number of serial schedules of n transactions: n!.

See Normalization and Indexing.

Discrete mathematics and probability

Formula	Meaning
Relations on an n-set	2^(n²); reflexive 2^(n² − n); symmetric 2^(n(n+1)/2)
Functions A → B, A has m and B has n elements	n^m; one-one n!/(n − m)!
Derangements D(n)	n! Σ (−1)^k / k!
Handshaking lemma	Σ degrees = 2 × edges
Euler's formula (planar connected)	V − E + F = 2
Bayes' theorem	P(A given B) = P(B given A) P(A) / P(B)
Binomial	mean np, variance np(1 − p)
Poisson	mean = variance = λ
Exponential	mean 1/λ, variance 1/λ²

See Combinatorics, Relations and Probability.

Check yourself

GATE-styleMCQ · one correct answer

Using the master theorem, T(n) = 8T(n/2) + n² is:

Θ(n²)
Θ(n² log n)
Θ(n³)
Θ(n⁴)

Show answer and explanation

Answer: C

a = 8, b = 2, k = 2: b^k = 4 < 8, so T(n) = Θ(n^(log₂ 8)) = Θ(n³).