GATE DA DBMS and Algorithms Formula Sheet with Traps

Q: How many comparisons does binary search make in the worst case?

On a sorted array of n elements, binary search makes at most ⌊ log₂ n ⌋ + 1 probes, from the recurrence T(n) = T(n/2) + 1. For 100 elements that is 6 + 1 = 7. The array must be sorted and allow random access, so binary search on a linked list loses its advantage.

Q: How do you calculate the order of a B+ tree?

An internal node with p pointers of P bytes and p - 1 keys of K bytes must fit in a block of B bytes, so pP + (p - 1)K ≤ B, which gives p = ⌊ (B + K)/(P + K) ⌋. With B = 1024, K = 12 and P = 8, the order is 51. Always take the floor, never round up.

Q: How many cuboids does a data cube have?

With n dimensions and no hierarchies, a data cube has 2ⁿ cuboids, one for every subset of dimensions. If dimension i has Lᵢ levels, not counting the top level all, the count is ∏ᵢ (Lᵢ + 1). In SQL, GROUP BY CUBE over n attributes forms 2ⁿ groupings, while ROLLUP forms only n + 1.

Q: What is the result of -7 // 2 in Python?

In Python 3, -7 // 2 is -4, because floor division rounds towards minus infinity, not towards zero. The remainder -7 % 2 is 1, since the remainder takes the sign of the divisor. True division 7 / 2 gives 3.5. Also note that round(2.5) gives 2, because ties go to the even integer.

Q: When is a decomposition lossless?

Splitting R into R₁ and R₂ is lossless exactly when the common attributes form a key of one side: R₁ ∩ R₂ → R₁ or R₁ ∩ R₂ → R₂ holds under the functional dependencies. A 3NF synthesis is always lossless and dependency-preserving. A BCNF decomposition is always lossless but may lose a dependency.

By MD ANISH AHAMADUpdated 4 Oct 20267 min read

GATE DA DBMS and Algorithms Formula Sheet with Traps

GATE DA's programming and database sections reward exact counts: comparisons, probes, nodes, edges, keys and cuboids. This sheet collects those formulas for algorithms and data structures, Python, relational databases and data warehousing. Each has its condition, a one-line example of my own and the trap beside it, all checked against the GATE DA 2027 book.

In this guide

Key takeaways
The terms this sheet uses
Searching and sorting
Data structures and hashing
Graphs
Python rules that decide answers
Relational algebra and SQL
Keys, normal forms and decomposition
Indexing, data preparation and warehousing
Using the sheet in the exam
Quick revision

Key takeaways

Selection sort always makes $\displaystyle \frac{n(n - 1)}{2}$ comparisons; insertion sort's shifts equal the number of inversions.
Dijkstra needs non-negative weights; Bellman–Ford allows negative ones and detects negative cycles.
Python floor division rounds towards minus infinity, and round sends ties to the even integer.
An attribute that never appears on a right-hand side belongs to every candidate key.
B+ tree order is a floor, never a rounded value.
$n$ dimensions give $2^n$ cuboids, but ROLLUP forms only $n + 1$ groupings.

The terms this sheet uses

$n$ is the number of elements and $\log_2$ the base-2 logarithm. $\Theta(f)$ means "grows exactly like $f$ ", and $O(f)$ means "at most like $f$ ". An inversion is a pair of elements in the wrong order. The load factor of a hash table is $\displaystyle \alpha = \frac{n}{m}$ , keys over slots.

In a database, a functional dependency $X \to Y$ says that equal $X$ values force equal $Y$ values. The closure $X^+$ is every attribute that $X$ determines. A superkey determines all attributes, and a candidate key is a minimal superkey. A cuboid is one grouping of a data cube.

Searching and sorting

Formula	Watch out for
Binary search worst case: $\lfloor \log_2 n \rfloor + 1$ probes	Sorted input with random access
Selection sort: $\displaystyle \frac{n(n - 1)}{2}$ comparisons always, at most $n - 1$ swaps	Sorted input does not help
Insertion sort: $n - 1$ comparisons sorted, $\displaystyle \frac{n(n - 1)}{2}$ reverse-sorted	Shifts equal inversions
Bubble sort with early exit: best $\Theta(n)$ ; swaps equal inversions	Each pass fixes the largest remaining
Merging lengths $m$ and $n$ : at most $m + n - 1$ comparisons	Mergesort needs $\Theta(n)$ extra space
Quicksort worst: $T(n) = T(n - 1) + \Theta(n) = \Theta(n^2)$	Sorted input with an end pivot
Stable: bubble, insertion, merge	Not stable: selection, quicksort

Examples: binary search on 100 elements needs at most 7 probes. Selection sort on 10 elements makes 45 comparisons and at most 9 swaps. Insertion sort on $(3, 1, 2)$ makes 2 shifts, one per inversion. Merging lists of 4 and 5 takes at most 8 comparisons.

The master theorem handles $T(n) = aT(n/b) + f(n)$ . Compare $f(n)$ with $n^{\log_b a}$ :

T(n) = \begin{cases} \Theta(n^{\log_b a}) & f \text{ smaller} \\ \Theta(n^{\log_b a}\log n) & f \text{ equal} \\ \Theta(f(n)) & f \text{ larger, regular} \end{cases}

So $4T(n/2) + n$ is $\Theta(n^2)$ , $2T(n/2) + n$ is $\Theta(n \log n)$ , and $T(n/2) + n^2$ is $\Theta(n^2)$ .

Data structures and hashing

Formula	Watch out for
Chaining: expected search $1 + \alpha$	$\alpha$ may exceed 1
Open addressing: unsuccessful at most $\displaystyle \frac{1}{1 - \alpha}$ ; successful at most $\displaystyle \frac{1}{\alpha}\ln\frac{1}{1 - \alpha}$	Needs $\alpha < 1$
Linear probing: $h(k, i) = (h(k) + i) \bmod m$	Primary clustering
Height $h$ in edges: $h + 1 \le \text{nodes} \le 2^{h+1} - 1$	Edges or levels? Check
Leaves $=$ (nodes with two children) $+ 1$	Holds for every binary tree
Binary tree shapes on $n$ nodes: $\displaystyle \frac{1}{n + 1}\binom{2n}{n}$	1, 2, 5, 14, 42 for $n = 1$ to 5
BST operations $O(h)$ , $\lfloor \log_2 n \rfloor \le h \le n - 1$	Sorted inserts make a chain

Examples: at $\alpha = 0.75$ , chaining expects 1.75 probes and open addressing at most 4 for a miss. A tree of height 3 has between 4 and 15 nodes. Six nodes with two children mean 7 leaves.

Trap: Preorder with postorder fixes a binary tree only when it is full. Inorder with either preorder or postorder always fixes it.

Graphs

Formula	Watch out for
$\sum \deg(v) = 2\lvert E \rvert$	The count of odd-degree vertices is even
Simple graph: at most $\displaystyle \frac{n(n - 1)}{2}$ edges; a tree has $n - 1$	A tree has exactly one path between two vertices
BFS and DFS: $O(V + E)$ with lists, $O(V^2)$ with a matrix	BFS gives fewest edges, not least weight
Back edge in DFS iff a cycle	Topological order iff a DAG
Dijkstra $O((V + E)\log V)$ with a heap, $O(V^2)$ with an array	Non-negative weights only
Bellman–Ford $O(VE)$ ; Floyd–Warshall $O(V^3)$	Bellman–Ford detects a reachable negative cycle

Example: five vertices with degrees summing to 14 have 7 edges. A simple graph on 6 vertices has at most 15 edges.

Python rules that decide answers

These are code, not formulas, but they decide answers just as exactly.

7 / 2 is 3.5; -7 // 2 is -4; -7 % 2 is 1. The remainder takes the divisor's sign.
round(2.5) is 2 and round(3.5) is 4: ties go to the even integer.
range(a, b) and s[i:j] stop before the end; s[::-1] reverses.
After b = a, a += [3] changes b too, while a = a + [3] does not.
def f(x, L=[]) creates L once, so calls share and grow the same list.

The book's last-minute sheet covers all seven technical sections like this, with every result's condition beside it. It is part of the GATE DA 2027 book, with 907 questions with worked solutions and 10 full mock tests.

Relational algebra and SQL

Formula	Watch out for
$\lvert R \times S \rvert = \lvert R \rvert \cdot \lvert S \rvert$	A natural join with no common attribute is a product
$R \cap S = R - (R - S)$	Union-compatible relations only
$R \div S = \pi_A(R) - \pi_A\big((\pi_A(R) \times S) - R\big)$	"Paired with every" value of $S$
$\neg \forall t\, P \equiv \exists t\, \neg P$	Safe tuple calculus equals relational algebra

SQL runs in the order FROM, WHERE, GROUP BY, HAVING, SELECT, DISTINCT, ORDER BY. Over the values $(4, \text{NULL}, 8)$ , COUNT(*) is 3, COUNT(col) is 2 and AVG is 6. Any comparison with NULL is unknown, so use IS NULL. NOT IN against a subquery containing NULL returns no rows.

Keys, normal forms and decomposition

Formula	Watch out for
$X$ is a superkey iff $X^+$ contains every attribute	Grow $X^+$ until nothing changes
2NF: no non-prime attribute depends on part of a key	Single-attribute keys pass automatically
3NF: for every non-trivial $X \to A$ , $X$ is a superkey or $A$ is prime	Prime means part of some candidate key
BCNF: for every non-trivial $X \to A$ , $X$ is a superkey	BCNF implies 3NF implies 2NF
Lossless iff $R_1 \cap R_2 \to R_1$ or $R_1 \cap R_2 \to R_2$	BCNF may lose a dependency

Example: $R(A, B, C, D, E)$ with $A \to B$ , $B \to C$ and $CD \to E$ . $A$ and $D$ appear on no right-hand side, and $\{A, D\}^+$ is every attribute, so $AD$ is the only key.

Indexing, data preparation and warehousing

Formula	Watch out for
B+ tree order $\displaystyle p = \left\lfloor \frac{B + K}{P + K} \right\rfloor$	Take the floor
Dense index: one entry per record; sparse: one per block	Sparse needs a sorted file
Min-max to $[a, b]$ : $\displaystyle v' = \frac{v - \min}{\max - \min}(b - a) + a$	Use the old range in the fraction
z-score: $\displaystyle v' = \frac{v - \bar{v}}{\sigma}$	Divide by the standard deviation, not the variance
Decimal scaling: $\displaystyle v' = \frac{v}{10^j}$ , smallest $j$ with every $\lvert v' \rvert < 1$	Choose $j$ from the largest absolute value
Equal-width bins: width $\displaystyle \frac{\max - \min}{k}$	Equal-frequency bins differ
Cuboids: $2^n$ ; with hierarchies $\prod_i (L_i + 1)$	`ROLLUP` gives $n + 1$ groupings

Examples: $B = 1024$ , $K = 12$ and $P = 8$ give $p = \lfloor 51.8 \rfloor = 51$ . The value 60 on a range 20 to 120 maps to 0.4 on $[0, 1]$ . With mean 50 and standard deviation 8, the value 70 has z-score 2.5. Three dimensions with 3, 2 and 1 levels give $4 \times 3 \times 2 = 24$ cuboids.

Remember: Count, sum, min and max are distributive; average is algebraic; median and mode are holistic. That three-way split decides how a measure rolls up.

Using the sheet in the exam

Count questions are mostly whole numbers, but normalisation answers are decimals; practise both on the GATE virtual calculator. Read the MCQ, MSQ and NAT marking scheme, common to every GATE paper before guessing on an MCQ. If you know the CS syllabus, GATE CS vs GATE DA shows where the database and algorithms core overlaps.

More formula sheets: all of GATE DA · Linear Algebra and Calculus · Machine Learning · Probability and Statistics

Quick revision

Binary search: $\lfloor \log_2 n \rfloor + 1$ probes.
Selection sort: $\displaystyle \frac{n(n - 1)}{2}$ comparisons always; insertion sort shifts equal inversions.
Chaining $1 + \alpha$ ; open addressing at most $\displaystyle \frac{1}{1 - \alpha}$ for a miss.
Dijkstra needs non-negative weights.
-7 // 2 is -4, and round(2.5) is 2.
An attribute on no right-hand side is in every key.
B+ tree order is $\displaystyle \left\lfloor \frac{B + K}{P + K} \right\rfloor$ .
Cuboids $2^n$ ; CUBE $2^n$ groupings, ROLLUP $n + 1$ .

Frequently asked questions

How many comparisons does binary search make in the worst case?

On a sorted array of $n$ elements, binary search makes at most $\lfloor \log_2 n \rfloor + 1$ probes, from the recurrence $T(n) = T(n/2) + 1$ . For 100 elements that is $6 + 1 = 7$ . The array must be sorted and allow random access, so binary search on a linked list loses its advantage.

How do you calculate the order of a B+ tree?

An internal node with $p$ pointers of $P$ bytes and $p - 1$ keys of $K$ bytes must fit in a block of $B$ bytes, so $pP + (p - 1)K \le B$ , which gives $\displaystyle p = \left\lfloor \frac{B + K}{P + K} \right\rfloor$ . With $B = 1024$ , $K = 12$ and $P = 8$ , the order is 51. Always take the floor, never round up.

How many cuboids does a data cube have?

With $n$ dimensions and no hierarchies, a data cube has $2^n$ cuboids, one for every subset of dimensions. If dimension $i$ has $L_i$ levels, not counting the top level all, the count is $\prod_i (L_i + 1)$ . In SQL, GROUP BY CUBE over $n$ attributes forms $2^n$ groupings, while ROLLUP forms only $n + 1$ .

What is the result of -7 // 2 in Python?