Core algorithm design paradigms including dynamic programming, greedy algorithms, divide and conquer, sorting, searching, and backtracking with decision guidance and trade-off analysis. Use when: selecting an algorithm paradigm for a new problem, teaching dynamic programming memoisation vs tabulation, reviewing greedy algorithm correctness, explaining divide-and-conquer recursion, analysing sorting algorithm choices, or recognising which algorithmic strategy applies to a given problem shape.
Core algorithm design paradigms including dynamic programming, greedy algorithms, divide and conquer, sorting, searching, and backtracking with decision guidance and trade-off analysis. Use when: selecting an algorithm paradigm for a new problem, teaching dynamic programming memoisation vs tabulation, reviewing greedy algorithm correctness, explaining divide-and-conquer recursion, analysing sorting algorithm choices, or recognising which algorithmic strategy applies to a given problem shape.
DSA Algorithm Paradigms
When to Use
Selecting the right algorithm paradigm before writing code
Teaching DP (memoisation vs tabulation) or explaining overlapping sub-problems
Reviewing greedy code for correctness (does local optimum imply global optimum?)
Analysing divide-and-conquer recursion depth and merge cost
Recognising backtracking as constrained exhaustive search
Sorting and Searching
Sorting Algorithm Reference
Algorithm
Best
Average
Worst
Space
Stable?
Merge sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Yes
Quick sort
O(n log n)
O(n log n)
O(n²)
O(log n)
No
Heap sort
O(n log n)
O(n log n)
O(n log n)
O(1)
No
Insertion sort
O(n)
O(n²)
O(n²)
O(1)
Yes
Introspective sort (.NET Array.Sort() / )
List<T>.Sort()
O(n log n)
O(n log n)
O(n log n)
O(log n)
No (not guaranteed)
.NET's Array.Sort() and List<T>.Sort() use an introspective sort variant and are not guaranteed stable. If you need a stable sort in .NET, LINQ's OrderBy is stable.
Binary Search
Binary search requires a sorted collection and halves the search space at each step.
// Canonical binary search templateint left = 0, right = array.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2; // avoids integer overflowif (array[mid] == target) return mid;
if (array[mid] < target) left = mid + 1;
else right = mid - 1;
}
return-1; // not found
Common variants:
Find first occurrence: when array[mid] == target, set right = mid - 1 and continue
Find insertion point: return left after the loop
Search on a function: binary search the answer space, not an array
Dynamic Programming
Two Signs That DP Applies
Overlapping sub-problems — the same smaller problem is solved multiple times
Optimal substructure — the optimal solution to the full problem is built from optimal sub-solutions
Memoisation (Top-Down)
var memo = new Dictionary<int, long>();
longFib(int n)
{
if (n <= 1) return n;
if (memo.TryGetValue(n, outvar cached)) return cached;
memo[n] = Fib(n - 1) + Fib(n - 2);
return memo[n];
}
Natural recursive structure — add cache to existing recursion
Space: O(n) cache + O(n) call stack
Tabulation (Bottom-Up)
long[] dp = newlong[n + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];
Iterative, no call stack overhead
Space: O(n); often reducible to O(1) for linear recurrences
Biotrackr Anchor — Report Caching as DP
CachingMcpToolWrapper stores tool results keyed by tool name + parameter hash. This is
tabulated DP applied to AI tool calls: if the same tool call (same inputs) was made before,
return the cached result rather than re-executing.
Teaching angle: Memoisation and caching are the same idea at different scales. DP memoises
recursive sub-problem results; a service cache memoises expensive computation results.
Both trade space for time.
Greedy Algorithms
When Greedy Works
A greedy algorithm makes the locally optimal choice at each step, hoping to reach a globally
optimal solution. It is correct only when the greedy choice property holds: local optima
compose into a global optimum.
Azure Container Apps and APIM apply greedy throttling: allow a request if quota remains,
reject immediately if not. This is a greedy policy — no lookahead, no reservation.
Teaching angle: Greedy works here because quota is consumed in the order of arrival and
there is no future information that would change the decision. If the problem were "maximise
the number of high-priority requests served given a quota window", greedy fails — you would
need DP or a priority queue.
Divide and Conquer
Pattern
Divide — split the problem into independent sub-problems
Conquer — solve each sub-problem recursively
Combine — merge sub-results into the final answer
Recurrence Analysis (Master Theorem)
For T(n) = aT(n/b) + O(n^d):
a > b^d: T(n) = O(n^log_b(a))
a = b^d: T(n) = O(n^d log n)
a < b^d: T(n) = O(n^d)
Merge sort: a=2, b=2, d=1 → a = b^d → O(n log n).
Biotrackr Anchor — Parallel Service Health Checks
Health checks across 14 Biotrackr services can run in parallel then be merged — divide
and conquer on the service graph:
Teaching angle: Divide-and-conquer is why Task.WhenAll is faster than sequential
awaits. You pay O(max individual duration) instead of O(sum of all durations). The
"merge" step is trivial (collect results), so the paradigm reduces to parallel fan-out.
Backtracking
Pattern
Backtracking is constrained exhaustive search — explore all candidate solutions,
prune branches that violate constraints early.
def backtrack(state, candidates):
if is_solution(state): record(state); return
for each candidate in candidates:
if is_valid(state + candidate):
apply(candidate)
backtrack(state + candidate, remaining)
undo(candidate) // backtrack
Use for: permutations, combinations, N-Queens, Sudoku, constraint satisfaction problems.
Note: Backtracking is inherently exponential — it is only practical when pruning
significantly reduces the search space.
