[Intermediate] — You can read a loop and count its iterations. You cannot do that with a recursive function, because its cost is defined in terms of itself. This lesson gives you the two tools that break that circularity: writing the cost as a recurrence relation, and drawing the recursion tree to solve it.
The payoff is that “what is the complexity of merge sort?” stops being something you remember and becomes something you can derive in thirty seconds on a whiteboard — including for an algorithm you have never seen.
Before you start
- You can write a recursive function and identify its base case and recursive case — recursion fundamentals.
- You can read and as statements about growth — growth and asymptotic notation.
- You know that a geometric series with ratio sums to a constant multiple of its first term, and one with ratio to a constant multiple of its last.
After this lesson you will be able to:
- Convert recursive code into a recurrence relation, correctly identifying the branching factor, the shrink factor, and the non-recursive work.
- Draw the recursion tree for a recurrence, and compute nodes, subproblem size and work for an arbitrary level.
- Decide which of three cases a recurrence falls into — leaves dominate, all levels equal, root dominates — and get the answer from that.
- Verify a claimed complexity empirically by doubling and checking the ratio.
Study route: sections 1–3 build the method; do the prediction in section 4 before reading on; section 5 is the pattern catalogue worth memorising; then run the lab.
1. Why this exists: the cost that refers to itself
Here is merge sort, stripped to its shape:
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid]) # sort half
right = merge_sort(a[mid:]) # sort the other half
return merge(left, right) # combine, in linear timeAsk “how long does this take on elements?” and you get: however long it takes on elements, twice, plus for the merge. The answer is written in terms of the question.
That is not a failure — it is the actual structure of the cost, and it has a standard notation:
In words: the time to sort items is the time to sort two halves, plus linear work to combine them. This is a recurrence relation: an equation defining a function in terms of its own smaller values. Solving it means finding a closed form — an expression for with no on the right-hand side.
The good news is that nearly every recurrence you meet in practice has one of three shapes, and you can tell which by asking a single question.
Terms used in recurrences
- Recurrence relation: This is an equation that defines a function’s value at using its values at smaller inputs, together with a base case. with is a recurrence.
- Closed form: This is also known as an explicit formula. This is an expression for that does not mention — for instance . Solving a recurrence means finding one, or at least its growth rate.
- Branching factor: This is written . This is how many recursive calls one call makes. Merge sort has ; binary search has ; the naive Fibonacci has .
- Shrink factor: This is written . This is the factor by which the input gets smaller in each call, when the shrinking is divisive. Merge sort has because each call gets half. A recursion that shrinks by subtraction — — has no , and is handled separately in section 6.
- Combine work: This is written . This is the non-recursive work one call does: everything outside the recursive calls. For merge sort , the cost of merging. It is also called the driving function.
- Recursion tree: This is a drawing of all the calls, with the original call at the root and each call’s subcalls as its children. Each node is labelled with the work that node alone does, excluding its children.
- Level: This is all the nodes at one depth of the recursion tree. Level 0 is the root. The key move in this lesson is computing the total work at a level, rather than per node.
- Depth: This is also called the height. This is the number of levels — how many times you can divide by before reaching the base case, which is for divisive recurrences and for subtractive ones.
- Leaves: These are the nodes at the bottom of the tree, where the base case applies. There are of them, which for divisive recurrences is .
- Substitution method: This is guessing a closed form and proving it correct by induction. It is the rigorous companion to the recursion tree, which is really a way of finding the guess.
2. From code to recurrence
Three things to read off the code, and nothing else:
- How many recursive calls? →
- How much smaller is the input in each? → (or “minus one”, for subtractive)
- How much work outside the recursive calls? →
Then .
| Code shape | Recurrence | |||
|---|---|---|---|---|
| Binary search: check middle, recurse into one half | 1 | 2 | ||
| Merge sort: two halves, linear merge | 2 | 2 | ||
| Naive Fibonacci: two calls, sizes and | 2 | — | ||
| Linear recursion: one call, one smaller | 1 | — | ||
| Tree traversal: two children, constant work | 2 | 2* |
* only for a balanced tree — an unbalanced one is , which is why traversal is by the simpler argument “each node is visited once” rather than by this machinery.
The mistake to avoid at this step is counting the recursive work twice. is only the work the current call does itself. In merge sort, the merge is ; the sorting of the halves is already accounted for by the term and must not be added again.
3. The recursion tree, and the only three answers
Draw the calls. Label each node with the work that node does itself. Then — and this is the move that makes the whole method work — sum across each level rather than down each branch.
For :
level 0: n 1 node x n = n
┌──────┴──────┐
level 1: n/2 n/2 2 nodes x n/2 = n
┌──┴──┐ ┌──┴──┐
level 2: n/4 n/4 n/4 n/4 4 nodes x n/4 = n
... ...
level k: 2^k nodes x n/2^k = n
...
level log n: 1 1 1 ... 1 1 1 n nodes x 1 = n
At level there are nodes, each of size , each doing work. The level total is regardless of . There are levels. Therefore
The lab measures exactly this table for : every level does 64 units of work, there are 7 levels, and the total is 448 — matching the closed form precisely.
The general level arithmetic
For , at level :
Everything depends on what that last quantity does as increases. It can only do three things, and each gives a different answer:
| If work per level… | Then the total is dominated by | Result |
|---|---|---|
| grows as you go down | the bottom level — the leaves | |
| stays constant | every level equally | |
| shrinks as you go down | the top level — the root |
This is the entire content of the Master Theorem, derived. The theorem is this table with the conditions made precise.
Why “dominated by” is legitimate
Because these are geometric series. If the work per level shrinks by a constant factor , the total is — a constant multiple of the root’s work, so the root’s work is the answer. If it grows by a factor , the last level is a constant fraction of the whole sum, so the leaves are the answer.
The lab makes both visible. For at , the level totals are — halving each time — and the total is 8,128, which is under . The root alone accounts for half the entire tree. For they run — doubling — total 127, and the bottom level alone is more than half.
4. Reading the three cases off a tree
Predict before reading on. For : at level there are nodes each of size , so the level work is . Is this dominated by the root, the leaves, or neither? And what is the resulting complexity?
The leaves. The level work is multiplied by at each step, so it grows downward and the bottom level dominates. The number of leaves is , so .
The lab confirms both halves. The level totals at are — each the last — with the leaf level at 729, which is exactly . Total work 2,059, matching the exact closed form .
And the doubling test confirms the growth rate independently: doubling multiplies the measured work by 3.06, 3.04, 3.03, 3.02 — converging on 3, which is what predicts, since .
That doubling test is the most useful practical skill in this lesson. If you think an algorithm is , double the input and see whether the time multiplies by . Linear doubles, quadratic quadruples, does slightly more than double, and barely moves. You can check a complexity claim in two runs without reading a line of the implementation.
5. The catalogue worth memorising
| Recurrence | Solution | Where you meet it |
|---|---|---|
| linear recursion, list sum | ||
| selection sort, quicksort’s worst case | ||
| subsets, towers of Hanoi | ||
| binary search | ||
| quickselect, average case | ||
| tree traversal, heapify | ||
| merge sort, quicksort average | ||
| root-dominated divide and conquer | ||
| Karatsuba multiplication | ||
| Strassen matrix multiplication |
The two rows worth staring at are rows 6 and 7. Same branching, same shrinking — the only difference is versus of combine work, and that alone is the difference between and . That is why merge sort cannot be made linear by clever coding: the merge is inherently linear, and a linear combine at every level is where the factor comes from.
Rows 1 and 4 are the other pair to internalise. Subtracting one gives levels; dividing by two gives levels. Shrinking multiplicatively rather than additively is the single highest-leverage move in algorithm design, and it is the reason binary search, balanced trees and divide-and-conquer all exist.
6. Subtractive recurrences, and where the tree method strains
does not fit the pattern, and the tree looks different: the depth is rather than , and the number of leaves is — exponential in whenever .
- : levels, constant each → .
- : levels, work → .
- : levels, work doubling each → .
The lesson of the third row: branching with subtractive shrinking is always exponential. This is naive Fibonacci, and it is why memoisation is not an optimisation there but a change of algorithm.
Verifying with the substitution method
The tree gives you a guess. Induction turns it into a proof. To show is , guess for some constant and all :
This is whenever , that is whenever . The inductive step holds; check a base case and you are done.
The step people get wrong is assuming the bound for without checking that the leftover terms cancel in the right direction. Here had to be , and that is what pinned down . If the leftovers had gone the other way, the guess would be wrong and would need strengthening — typically to .
7. Worked example — complete runnable lab
Save as recursion_trees.py. Standard library only. It does not run the real algorithms — it simulates the recurrences directly, so the level tables are exact rather than timing-dependent.
"""Draw the recursion tree by measuring it: work per level, for real recurrences.
Run: python3 recursion_trees.py
"""
import math
from collections import defaultdict
def run(a, b, f, n):
"""Simulate T(n) = a*T(n/b) + f(n) and record the work done at each level.
a = number of subcalls, b = shrink factor, f = non-recursive work at size n.
Returns (total_work, work_by_level).
"""
by_level = defaultdict(float)
def rec(size, level):
by_level[level] += f(size)
if size <= 1:
return
for _ in range(a):
rec(size / b, level + 1)
rec(n, 0)
return sum(by_level.values()), dict(sorted(by_level.items()))
def level_table(a, b, f, n, label, closed_form):
total, levels = run(a, b, f, n)
print(f"\n {label} (n = {n})")
print(" level | nodes | size each | work this level")
for lvl, work in levels.items():
nodes = a ** lvl
size = n / (b ** lvl)
print(f" {lvl:>5} | {nodes:>7} | {size:>9.1f} | {work:>17,.0f}")
print(f" total work: {total:,.0f}")
print(f" closed form {closed_form[0]}: {closed_form[1](n):,.0f}")
return total
def growth_check(a, b, f, label, predicted):
"""Double n repeatedly; report total work and the ratio between successive runs."""
print(f"\n {label}")
print(" n | total work | ratio vs previous | predicted ratio")
prev = None
for n in (64, 128, 256, 512, 1024):
total, _ = run(a, b, f, n)
ratio = f"{total/prev:>17.2f}" if prev else f"{'-':>17}"
pr = predicted(n) / predicted(n / 2) if n > 64 else None
pr_s = f"{pr:>15.2f}" if pr else f"{'-':>15}"
print(f" {n:>7} | {total:>15,.0f} | {ratio} | {pr_s}")
prev = total
def main():
print("=== 1. T(n) = 2T(n/2) + n -- every level does the same work ===")
level_table(2, 2, lambda s: s, 64,
"merge sort's recurrence", ("n*(log2(n)+1)", lambda n: n * (math.log2(n) + 1)))
print(" -> n work per level, log2(n)+1 levels => O(n log n)")
print("\n=== 2. T(n) = 2T(n/2) + 1 -- the LEAVES dominate ===")
level_table(2, 2, lambda s: 1, 64,
"constant work per node", ("2n-1", lambda n: 2 * n - 1))
print(" -> work DOUBLES each level; the bottom level alone is half the total => O(n)")
print("\n=== 3. T(n) = 2T(n/2) + n^2 -- the ROOT dominates ===")
level_table(2, 2, lambda s: s * s, 64,
"quadratic combine", ("2n^2 - n", lambda n: 2 * n * n - n))
print(" -> work HALVES each level; the root alone is half the total => O(n^2)")
print("\n=== 4. T(n) = T(n/2) + 1 -- one branch only ===")
level_table(1, 2, lambda s: 1, 64,
"binary search", ("log2(n)+1", lambda n: math.log2(n) + 1))
print(" -> one node per level, log2(n)+1 levels => O(log n)")
print("\n=== 5. T(n) = 3T(n/2) + n -- branching beats shrinking ===")
level_table(3, 2, lambda s: s, 64,
"Karatsuba-shaped", ("3*n^log2(3) - 2n", lambda n: 3 * n ** math.log2(3) - 2 * n))
print(" -> work grows by 3/2 each level; leaves dominate => O(n^log2(3))")
print("\n\n=== 6. Verifying the growth rates by doubling n ===")
print(" If T(n) is O(n^k), doubling n multiplies the work by 2^k.")
growth_check(2, 2, lambda s: s, "T(n) = 2T(n/2) + n -> expect just over 2.0",
lambda n: n * math.log2(n))
growth_check(2, 2, lambda s: 1, "T(n) = 2T(n/2) + 1 -> expect 2.0 (linear)",
lambda n: n)
growth_check(2, 2, lambda s: s * s, "T(n) = 2T(n/2) + n^2 -> expect 4.0 (quadratic)",
lambda n: n * n)
growth_check(3, 2, lambda s: s, "T(n) = 3T(n/2) + n -> expect 3.0 (n^1.585)",
lambda n: n ** math.log2(3))
print("\n\n=== 7. The three shapes, side by side ===")
print(" What decides the answer is how work changes as you go DOWN the tree:")
print(" work grows downward -> the LEAVES dominate -> total = O(leaves)")
print(" work is constant -> every level is equal -> total = O(f(n) * depth)")
print(" work shrinks downward -> the ROOT dominates -> total = O(f(n))")
print()
print(" recurrence | work per level | dominated by | result")
print(" 2T(n/2) + 1 | 1, 2, 4, ... n | leaves | O(n)")
print(" 2T(n/2) + n | n, n, n, ... n | all equal | O(n log n)")
print(" 2T(n/2) + n^2 | n^2, n^2/2, ... | root | O(n^2)")
print(" 3T(n/2) + n | n, 1.5n, 2.25n... | leaves | O(n^1.585)")
if __name__ == "__main__":
main()Expected output
Generated by running the file above:
=== 1. T(n) = 2T(n/2) + n -- every level does the same work ===
merge sort's recurrence (n = 64)
level | nodes | size each | work this level
0 | 1 | 64.0 | 64
1 | 2 | 32.0 | 64
2 | 4 | 16.0 | 64
3 | 8 | 8.0 | 64
4 | 16 | 4.0 | 64
5 | 32 | 2.0 | 64
6 | 64 | 1.0 | 64
total work: 448
closed form n*(log2(n)+1): 448
-> n work per level, log2(n)+1 levels => O(n log n)
=== 2. T(n) = 2T(n/2) + 1 -- the LEAVES dominate ===
constant work per node (n = 64)
level | nodes | size each | work this level
0 | 1 | 64.0 | 1
1 | 2 | 32.0 | 2
2 | 4 | 16.0 | 4
3 | 8 | 8.0 | 8
4 | 16 | 4.0 | 16
5 | 32 | 2.0 | 32
6 | 64 | 1.0 | 64
total work: 127
closed form 2n-1: 127
-> work DOUBLES each level; the bottom level alone is half the total => O(n)
=== 3. T(n) = 2T(n/2) + n^2 -- the ROOT dominates ===
quadratic combine (n = 64)
level | nodes | size each | work this level
0 | 1 | 64.0 | 4,096
1 | 2 | 32.0 | 2,048
2 | 4 | 16.0 | 1,024
3 | 8 | 8.0 | 512
4 | 16 | 4.0 | 256
5 | 32 | 2.0 | 128
6 | 64 | 1.0 | 64
total work: 8,128
closed form 2n^2 - n: 8,128
-> work HALVES each level; the root alone is half the total => O(n^2)
=== 4. T(n) = T(n/2) + 1 -- one branch only ===
binary search (n = 64)
level | nodes | size each | work this level
0 | 1 | 64.0 | 1
1 | 1 | 32.0 | 1
2 | 1 | 16.0 | 1
3 | 1 | 8.0 | 1
4 | 1 | 4.0 | 1
5 | 1 | 2.0 | 1
6 | 1 | 1.0 | 1
total work: 7
closed form log2(n)+1: 7
-> one node per level, log2(n)+1 levels => O(log n)
=== 5. T(n) = 3T(n/2) + n -- branching beats shrinking ===
Karatsuba-shaped (n = 64)
level | nodes | size each | work this level
0 | 1 | 64.0 | 64
1 | 3 | 32.0 | 96
2 | 9 | 16.0 | 144
3 | 27 | 8.0 | 216
4 | 81 | 4.0 | 324
5 | 243 | 2.0 | 486
6 | 729 | 1.0 | 729
total work: 2,059
closed form 3*n^log2(3) - 2n: 2,059
-> work grows by 3/2 each level; leaves dominate => O(n^log2(3))
=== 6. Verifying the growth rates by doubling n ===
If T(n) is O(n^k), doubling n multiplies the work by 2^k.
T(n) = 2T(n/2) + n -> expect just over 2.0
n | total work | ratio vs previous | predicted ratio
64 | 448 | - | -
128 | 1,024 | 2.29 | 2.33
256 | 2,304 | 2.25 | 2.29
512 | 5,120 | 2.22 | 2.25
1024 | 11,264 | 2.20 | 2.22
T(n) = 2T(n/2) + 1 -> expect 2.0 (linear)
n | total work | ratio vs previous | predicted ratio
64 | 127 | - | -
128 | 255 | 2.01 | 2.00
256 | 511 | 2.00 | 2.00
512 | 1,023 | 2.00 | 2.00
1024 | 2,047 | 2.00 | 2.00
T(n) = 2T(n/2) + n^2 -> expect 4.0 (quadratic)
n | total work | ratio vs previous | predicted ratio
64 | 8,128 | - | -
128 | 32,640 | 4.02 | 4.00
256 | 130,816 | 4.01 | 4.00
512 | 523,776 | 4.00 | 4.00
1024 | 2,096,128 | 4.00 | 4.00
T(n) = 3T(n/2) + n -> expect 3.0 (n^1.585)
n | total work | ratio vs previous | predicted ratio
64 | 2,059 | - | -
128 | 6,305 | 3.06 | 3.00
256 | 19,171 | 3.04 | 3.00
512 | 58,025 | 3.03 | 3.00
1024 | 175,099 | 3.02 | 3.00
=== 7. The three shapes, side by side ===
What decides the answer is how work changes as you go DOWN the tree:
work grows downward -> the LEAVES dominate -> total = O(leaves)
work is constant -> every level is equal -> total = O(f(n) * depth)
work shrinks downward -> the ROOT dominates -> total = O(f(n))
recurrence | work per level | dominated by | result
2T(n/2) + 1 | 1, 2, 4, ... n | leaves | O(n)
2T(n/2) + n | n, n, n, ... n | all equal | O(n log n)
2T(n/2) + n^2 | n^2, n^2/2, ... | root | O(n^2)
3T(n/2) + n | n, 1.5n, 2.25n... | leaves | O(n^1.585)
What the lab is demonstrating
- Blocks 1–5 are the level tables. Read the rightmost column downward in each: constant in block 1, doubling in block 2, halving in block 3, constant-at-one in block 4, growing by in block 5. That column alone determines the answer, and the closed form printed underneath matches the measured total exactly in every case.
- Block 6 is the doubling test.
2T(n/2)+1gives a ratio of exactly 2.00 (linear),2T(n/2)+n^2gives 4.00 (quadratic),3T(n/2)+ngives 3.02 (that is ), and2T(n/2)+ngives 2.20 and falling — just over 2, which is the signature of , and the measured ratio tracks the predicted one to two decimal places. - The ratio for decreases as grows (2.29 → 2.20). That is correct and worth understanding: the ratio is , which approaches 2 from above. An algorithm whose doubling ratio slowly falls toward 2 is , not linear.
8. Common pitfalls and traps
- Counting the recursive work inside . is only what the current call does itself. Including the subcalls double-counts the entire tree.
- Assuming the tree is balanced when it is not. Quicksort is , and depends on the pivot. The figure assumes balanced splits; the worst case gives . A recursion tree drawn as balanced silently assumes the thing you may need to prove.
- Forgetting that the depth of a subtractive recurrence is , not . is ; is . The two look almost identical written down and differ by an exponential.
- Reading as base 10 or base . Inside the base is irrelevant — logs differ by a constant factor. In the level arithmetic it is not: the depth really is with the shrink factor, and that is what tells you a 3-way split has depth .
- Assuming more branching is always worse. is , and Strassen’s is — one fewer subcall changes the exponent. Branching interacts with shrinking; neither alone decides.
- Trusting the guess without the induction. The tree method is a heuristic for finding the answer. For an unfamiliar recurrence, verify by substitution or by the doubling test.
- Ignoring the base case’s contribution. For the leaves are the whole cost — there are of them each doing constant work. If you only count the internal nodes you will conclude and be badly wrong.
9. Check your understanding
-
. Root, leaves, or balanced — and what is the answer?
Answer
Level work is $4^k \cdot n/2^k = n \cdot 2^k$, which grows downward, so the leaves dominate. Leaves number $4^{\log_2 n} = n^{\log_2 4} = n^2$. So $T(n) = \Theta(n^2)$. Doubling $n$ should multiply the work by 4. -
Two algorithms: and . Which is faster, and by how much?
Answer
The second, by a factor of $\log n$ — it is $O(n)$ against $O(n\log n)$. The only difference is the combine step, and it costs a whole logarithmic factor because it is paid at every one of the $\log n$ levels. This is precisely the gap between merge sort and a tree traversal. -
Why is naive Fibonacci rather than , and why do we usually say anyway?
Answer
$T(n) = T(n-1) + T(n-2) + O(1)$ does not branch into two equal halves — one subtree is shorter — so the count grows as the golden ratio $\varphi \approx 1.618$ rather than 2. Precisely, the call count is $2\,\mathrm{fib}(n+1)-1$. We say $O(2^n)$ because it is a correct upper bound, it is the right order of magnitude, and the distinction rarely changes a decision. The lab's measured counts follow the $\varphi$ growth, not $2^n$: 2,692,537 at $n=30$, where $2^{30}$ is about a billion. -
You suspect an implementation is . It takes 1.0s at and 4.1s at . Confirmed or not?
Answer
Consistent with $O(n^2)$: doubling $n$ quadrupled the time, and $4.1 \approx 4$. But one data point is weak evidence — $n\log n$ with a bad constant can look similar over a single doubling. Take a third point at $n=4000$: quadratic predicts about 16.4s, $n\log n$ predicts about 9s. The ratios diverge fast, which is why three points beat two. -
A recurrence has level work but depth instead of . What is ?
Answer
$O(n^{1.5})$ — the level arithmetic is unchanged, total is work-per-level times depth, $n \cdot \sqrt{n}$. This is the point of the method: you are never pattern-matching on named recurrences, you are multiplying a per-level cost by a number of levels. This shape arises from $T(n) = T(n - \sqrt{n}) + n$.
10. Practice — independent task
Build a recurrence solver you can check against reality.
Part 1 — the simulator. Write solve(a, b, f, n) returning total work and a per-level breakdown, as the lab’s run does — but write it yourself before reading that function. It must handle and non-integer sizes.
Part 2 — the classifier. Write classify(a, b, f, n) that decides, from measurements only, whether the recurrence is root-dominated, balanced, or leaf-dominated. Compare the work at level 0 with the work at the deepest level, and with the total. State the threshold you chose and defend it.
Part 3 — against real code. Instrument actual implementations of binary search, merge sort and a balanced-tree traversal to count their real operations. Check the counts against your simulator’s prediction for the matching recurrence. They should agree to within a constant factor; if they do not, one of the two is wrong and finding out which is the exercise.
Part 4 — the doubling test. Write growth_exponent(fn, sizes) that runs a function at doubling sizes and returns the estimated exponent such that the cost is , by taking of the ratio between successive runs. Test it on known , and functions and report how close it gets.
Edge cases: (no branching); ; smaller than ; not dividing evenly; a recurrence whose depth is 1.
Done when: your classifier agrees with the hand analysis on all ten rows of the section 5 catalogue; your part 3 counts match predictions to within a constant factor you can state; and your doubling test reports an exponent within 0.1 of the truth for the three test functions — and you can explain why it reports about 1.1 rather than 1.0 for an function.
Before moving on
You can turn recursive code into a recurrence, draw its tree, compute the work at an arbitrary level, decide which of the three cases applies, and verify the result by doubling the input.
Recap: read , and off the code to get . At level there are nodes of size , so the level work is — and the way that quantity moves as you descend is the whole answer. Growing downward means the leaves dominate, giving ; constant means every level is equal, giving ; shrinking means the root dominates, giving . Subtractive recurrences have depth rather than , so branching plus subtraction is always exponential. Confirm any claim by doubling : linear doubles, quadratic quadruples, and gives a ratio slightly above 2 that falls slowly toward it.
Next: The Master Theorem — the three cases above, stated as a theorem with precise conditions, so you can skip the tree when the recurrence is a standard shape.
Related
- Recursion Fundamentals — the previous lesson
- The Master Theorem — this lesson’s three cases, formalised
- Divide and Conquer — the algorithm family these recurrences describe
- Growth and Asymptotic Notation — the notation being solved for
- Merge Sort · Quicksort — the worked cases
- Discrete maths: induction and recursion — the substitution method’s proof machinery
- the recursion folder
Software engineering
Infrastructure & security
Computer science
Hardware & engineering