GATE CSE Formula Sheet: Key Formulas for Every Subject

This GATE CSE formula sheet collects key formulas that past GATE papers have tested repeatedly, grouped by subject, with the trap to watch for where it matters most. It is a free selection from the book's last-minute revision sheet. Use it to check your recall, then practise each formula on previous-year questions.

Key takeaways

• Many GATE CSE numerical questions reuse the same formulas with new numbers.
• A formula is only useful with its conventions: $\log$ base 2, powers of two for memory, $10^6$ for Mbps unless stated.
• Many traps are off-by-one errors: $(k + n - 1)$ cycles, $2^m - 1$ windows, $n(k - 1) + 1$ resources.
• You cannot carry paper into the exam (confirm current rules at gate2027.iitm.ac.in), so formulas must be in memory.

How to read this sheet

Notation: $\log$ means $\log_2$ unless written $\ln$; $\lceil x \rceil$ and $\lfloor x \rfloor$ are ceiling and floor; $\binom{n}{k}$ is the binomial coefficient; $x^y$ is $x$ to the power $y$. For memory sizes, KB means $2^{10}$ unless the question says otherwise; for data rates, Mbps means $10^6$ bits per second unless stated.

Operating System

For how these formulas turn into questions, see Operating Systems for GATE CSE 2027.

Computer Organization and Architecture

• $\text{offset} = \log_2 B$; $\displaystyle \text{sets} = \frac{C}{k \times B}$; $\text{index} = \log_2(\text{sets})$; $\text{tag} = A - \text{index} - \text{offset}$ ($B$ block bytes, $C$ cache bytes, $k$ associativity, $A$ address bits; fully associative has $\text{index} = 0$)
• $\text{AMAT} = t_1 + m_1\big(t_2 + m_2\,(t_3 + m_3\,t_{\text{mem}})\big)$ (local miss rates; add lower-level time only on a miss)
• Cycle $\tau = \text{max stage delay} + \text{latch delay}$; $T_{\text{pipe}}(n) = (k + n - 1)\,\tau$; $T_{\text{nonpipe}}(n) = n \times (\text{sum of stage delays})$
• Branch: $\text{CPI} = 1 + f_b\,(1 - p) \times \text{penalty}$ ($f_b$ branch fraction, $p$ predictor accuracy)
• $\text{Overflow flag} = C_{\text{in}} \oplus C_{\text{out}}$ of the MSB

Computer Networks

The patterns behind these are covered in Computer Networks for GATE CSE 2027.

Databases

• Internal node: $p \times \text{ptr} + (p - 1) \times \text{key} \le B$, so $\displaystyle p = \left\lfloor \frac{B + \text{key}}{\text{ptr} + \text{key}} \right\rfloor$; leaf: $k \times (\text{key} + \text{recptr}) + \text{ptr} \le B$, so $\displaystyle k = \left\lfloor \frac{B - \text{ptr}}{\text{key} + \text{recptr}} \right\rfloor$
• Levels for $N$ records with fan-out $f$: $\lceil \log_f N \rceil$ (including leaves); block accesses $= \text{levels} + 1$ for the data block
• Super keys with one candidate key of size $k$ over $n$ attributes $= 2^{n-k}$
• Lossless binary decomposition iff $(R_1 \cap R_2) \to R_1$ or $(R_1 \cap R_2) \to R_2$ in $F^+$; dependency preserving iff $(F_1 \cup F_2)^+ = F^+$
• Interleavings of two transactions with $m$ and $n$ operations $= \binom{m + n}{m}$

This page gives a selection. The book's last-minute revision sheet has full formula tables for all ten subjects, each row with symbols, when the formula applies and its typical trap, plus the top 50 concepts, the most-asked algorithms step by step, a traps table, edge cases and an exam-day checklist. It is part of the GATE CSE 2027 book.

Algorithms

Standard recurrences, each result a $\Theta$ bound:

• Master theorem trap: $2T(n/2) + n \log n$ is Case 2 with $k = 1$, so $\Theta(n \log^2 n)$, not $n \log n$
• Max and min together: $\lceil 3n/2 \rceil - 2$; second largest: $n + \lceil \log_2 n \rceil - 2$; binary search worst: $\lfloor \log_2 n \rfloor + 1$ comparisons
• Catalan $\displaystyle C_n = \frac{1}{n + 1}\binom{2n}{n}$: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796 for $n = 0, \dots, 10$ (BSTs on $n$ keys, stack permutations)
• Build-heap: $\lfloor n/2 \rfloor$ sift-downs, at most $2n$ comparisons, $\Theta(n)$

Discrete and Engineering Mathematics

• $v - e + f = 2$ (connected planar; $f$ counts the outer face); $e \le 3v - 6$ ($v \ge 3$); bipartite or triangle-free planar $e \le 2v - 4$
• Spanning trees: $K_n$ has $n^{n-2}$; $K_{m,n}$ has $m^{n-1} \times n^{m-1}$; $C_n$ has $n$
• Relations on an $n$-set: $2^{n^2}$; reflexive: $2^{n^2 - n}$; symmetric: $2^{n(n+1)/2}$; reflexive and symmetric: $2^{n(n-1)/2}$
• Eigenvalues: sum $=$ trace, product $= \det A$; $A^k$ has $\lambda^k$, $A^{-1}$ has $1/\lambda$, $A + cI$ has $\lambda + c$
• Bayes: $\displaystyle P(A_i \mid B) = \dfrac{P(B \mid A_i)\,P(A_i)}{\sum_j P(B \mid A_j)\,P(A_j)}$
• $\text{Uniform}(a, b)$: mean $\displaystyle \frac{a + b}{2}$, variance $\displaystyle \frac{(b - a)^2}{12}$; $\text{Exponential}(\lambda)$: mean $\displaystyle \frac{1}{\lambda}$, variance $\displaystyle \frac{1}{\lambda^2}$

Digital Logic

• $n$-bit 2's complement range: $-2^{n-1}$ to $2^{n-1} - 1$
• IEEE-754 single: 1 sign, 8 exponent (bias 127), 23 fraction; $\text{value} = (-1)^S \times 1.F \times 2^{E - 127}$ for $1 \le E \le 254$
• Functions of $n$ variables: $2^{2^n}$; self-dual: $2^{2^{n-1}}$
• Counter: mod-$N$ needs $\lceil \log_2 N \rceil$ flip-flops; ring counter with $n$ flip-flops has $n$ states, Johnson $2n$

Theory of Computation

• $\#a \equiv r \pmod{p}$: $p$ states; $\#a \bmod p$ and $\#b \bmod q$ independent: $p \times q$
• Contains $w$ as a substring: $\lvert w \rvert + 1$; ends with $w$: $\lvert w \rvert + 1$; starts with $w$: $\lvert w \rvert + 2$ (dead state); $k$-th symbol from the right is $a$: $2^k$ (NFA $k + 1$)
• NFA with $n$ states: minimal DFA has at most $2^n$ states
• CNF derivation of a string of length $n$ takes exactly $2n - 1$ steps; GNF takes $n$

Compiler Design

• LR(0) items $= \sum_{\text{productions}} \big(\lvert \text{RHS} \rvert + 1\big)$, including $S' \to S$ which contributes 2; an $\varepsilon$-production contributes 1
• LALR states $=$ LR(0)/SLR states; merging can add only reduce–reduce conflicts
• $\text{live-in}(B) = \text{use}(B) \cup \big(\text{live-out}(B) - \text{def}(B)\big)$; $\text{live-out}(B) = \bigcup \text{live-in}(\text{successors})$
• Basic-block leaders: the first instruction; any jump target; any instruction immediately after a jump (conditional or unconditional)

Programming and Data Structures

• Row-major $A[i][j]$ with bounds $[l_1 \ldots u_1][l_2 \ldots u_2]$: $\text{base} + \big((i - l_1) \times (u_2 - l_2 + 1) + (j - l_2)\big) \times w$
• Full (strict) binary tree: $L = I + 1$, $n = 2L - 1$; $k$-ary strict tree: $L = (k - 1)\,I + 1$, $n = kI + 1$
• Heap (1-based): parent $\lfloor i/2 \rfloor$, children $2i$ and $2i + 1$; 0-based: parent $\lfloor (i - 1)/2 \rfloor$, children $2i + 1$ and $2i + 2$
• Binary tree of height $h$ (edges): max nodes $2^{h+1} - 1$, min nodes $h + 1$

Subject-wise formula sheets

Each of these goes deeper on one part of the GATE CSE paper, with a worked example and the trap for every formula:

• Computer Networks formula sheet
• COA formula sheet
• Engineering Mathematics formula sheet
• Operating Systems formula sheet

How to revise with a formula sheet

1. Read it daily in the final two weeks, and once more on the morning of the exam.
2. Attach a trap to every formula. Knowing $(k + n - 1)$ is half the job; knowing that $k \times n$ is the classic wrong answer is the other half. Common mistakes that cost marks in GATE CSE lists the traps subject by subject.
3. Write the unit next to every number. ms versus µs versus ns, KB as 1,000 or 1,024, bits versus bytes. Unit slips are a common cause of wrong NAT answers.
4. Carry full precision. Round only the final answer, to the decimals the question asks for. The MCQ, MSQ and NAT strategy guide covers answer entry for each type.
5. Use the rough sheet early. In the first five minutes, write the few formulas you are most likely to forget under pressure, such as the effective access time formula, $(k + n - 1)$, the Go-Back-N and Selective Repeat window limits, and the minimum-resources formula.

To place this inside a full revision schedule, follow the GATE CSE last-month revision plan.