Algorithm Analysis, AVL Trees & B-Trees – Comprehensive Notes

Introduction to Algorithm Analysis

• Algorithm = finite set of unambiguous instructions that always terminates & is executable by hand.
  • INPUT ➜ zero or more externally supplied values.
  • OUTPUT ➜ at least one value produced.
  • DEFINITENESS ➜ every step is clear & unambiguous.
  • FINITENESS ➜ terminates after a finite number of steps for every instance.
  • EFFECTIVENESS ➜ each step is simple enough to be carried out with pencil-and-paper.

Why analyse algorithms?

• Predict behaviour without coding / machine-specific tests.
• Provides simple, machine-independent efficiency measures.
• Exact prediction impossible ⇒ analysis is an approximation.
• Enables comparison & selection of best algorithm for a task.

Types of analysis

1. Best case
   • Lowest run-time; lower bound on complexity.
   • Ex: linear search finds key at first position.
2. Worst case
   • Highest run-time; upper bound.
   • Ex: linear search misses key in entire array.
3. Average case
   • \text{Avg} = \dfrac{\sum\text{time over all inputs}}{\text{#inputs}}

Space and Time Complexity Analysis

Space complexity

• Total memory required = fixed part + variable part.
  • Fixed part: code, constants, simple variables, fixed-size aggregates.
  • Variable part: input-dependent structures, referenced data, recursion stack.
• Formal model: $S(P)=c+S_P(\text{instance characteristics})$
• Example

  double sum(double a[], int n){
      double s=0.0;
      for(int i=1;i<=n;i++) s+=a[i];
      return s;
  }

• Needs space for array $a$ (≥$n$ words), variables $n,i,s$ (3 words).
• $S_{sum}(n)\ge n+3$ words.

Time complexity (run time)

• $T(P)=\text{compile time}+t_P(\text{instance})$ (compile time ignored once program is reused).
• Step counting rules (primitive assignment = 1, comments = 0, loop control ≈ 1 per iteration, etc.).

Counting method 1 – instrument code

s = 0.0;      // count+=1
for(i=1;i<=n;i++){ // count +=1 each test (n+1 times)
    s = s + a[i];  // count+=1 executed n times
}
return s;        // count+=1

• Total steps after termination $=2n+3$.

Counting method 2 – table

Asymptotic Notations

Big-O $O(\,)$ – upper bound

• $f(n)=O(g(n)) \iff \exists\,c>0,n<em>0:\; f(n)\le c\,g(n)\;\forall n\ge n</em>0$
• Example: $3n+2=O(n)$ with $c=4,n_0=2$.

Omega $\Omega(\,)$ – lower bound

• $f(n)=\Omega(g(n)) \iff \exists\,c>0,n<em>0:\; f(n)\ge c\,g(n)\;\forall n\ge n</em>0$
• Example: $3n+2=\Omega(n)$ with $c=3,n_0=1$.

Theta $\Theta(\,)$ – tight bound

• $f(n)=\Theta(g(n)) \iff \exists\,c<em>1,c</em>2>0,n<em>0:\; c</em>1g(n)\le f(n)\le c<em>2g(n) \;\forall n\ge n</em>0$
• Example: $3n+2=\Theta(n)$ with $c<em>1=3,c</em>2=4,n_0=2$.

Little-o $o(\,)$ – non-tight upper bound

• $f(n)=o(g(n)) \iff \lim_{n\to\infty} \dfrac{f(n)}{g(n)}=0$.
• For any $c>0,\exists n<em>0: 0\le f(n)<c\,g(n)$ beyond $n</em>0$.
• Example: $7n+8 \in o(n^2)$ because ratio $\rightarrow 0$ as $n\to\infty$.

AVL Trees

Definition & balance factor

• Height-balanced BST (invented 1962 by Adelson-Velsky & Landis).
• For every node: $\text{BF}=h<em>{left}-h</em>{right}\in{-1,0,1}$ (alternate sign convention allowed).
• Every AVL is a BST; the converse is false.

Rotations (re-balancing primitives)

1. Single Left (LL) – right rotation about pivot; fixes left-left heavy.
2. Single Right (RR) – left rotation; fixes right-right heavy.
3. Left-Right (LR) – RR on left child then LL on pivot.
4. Right-Left (RL) – LL on right child then RR on pivot.

Operations

Creation

1. Start with $root=null$.
2. Insert nodes via BST rule; after each insertion update heights & BF; rotate if needed.

Insertion algorithm ((O(\log n)))

• Insert new key as leaf using BST search.
• Walk back up, update heights, compute BF.
• If a node violates BF, perform appropriate rotation (LL, RR, LR, RL) centred at first unbalanced ancestor.

Example: inserting 1→8

• Sequence of states shows LL, LR rotations; final tree perfectly balanced with height 3.

Deletion algorithm

• Delete like BST, then backtrack updating heights & BF.
• If imbalance appears, use L or R family of rotations determined by location of deletion relative to critical node.
  • R0: child BF 0.
  • R1: child BF +1.
  • R−1: child BF −1 (equivalent to LR case).
• Examples: deleting 30 (R0), 55 (R1), 60 (R−1) illustrated.

Applications

• Situations with few updates but many searches.
• In-memory sets/dictionaries, symbol tables, gaming storyline data, any search-intensive app.
• Databases for small main-memory indices where order of input may be nearly sorted.

B-Trees

Definition & properties (order $m$)

• Generalised $m$-way search tree optimised for disk/block access.
• Max keys/node: $m-1$; max children: $m$.
• Except root & leaves, every node has $\ge \lceil m/2 \rceil$ children.
• Root has at least 2 children unless it is a leaf.
• All leaves appear on same level (tree is perfectly height-balanced).

Why B-tree?

• Stores many keys per node ⇒ reduces height ⇒ minimises expensive disk I/O.

Operations

Creation

1. Fix order $m$.
2. Start with empty root.

Insertion (at leaf)

1. Search down to proper leaf.
2. If leaf has $<m-1$ keys: insert in sorted order.
3. Else (overflow):
   • Insert key then split at median.
   • Median key moves up; split may propagate recursively. If root overflows, new root is created (height +1).

Example: order 3, insert 1-10

• Shows successive splits at 3, 6; root promotions (2 then 4) etc.; final height 3 tree.

Example: order 5, insert 8 into node with 4 keys ⇒ overflow ⇒ split around median 8 and push up.

Deletion

• Always affect a leaf first (internal key replaced by in-order predecessor/successor from leaf).
• After deletion, if a node still has $\ge\lceil m/2 \rceil$ keys: done.
• Otherwise (underflow):
  1. Borrow from left/right sibling with >min keys via rotation through parent separator.
  2. Else merge with sibling + separator, reducing parent’s keys. If parent underflows, repeat upward; if root ends with 0 keys, height decreases.

Example (order 5, delete 5,12,32,53)

1. Delete 5 → simple shift.
2. Delete 12 → borrow from left sibling via separator 11.
3. Delete 32 → borrow from right sibling via separator 51.
4. Delete 53 (internal) → replace by successor 61, then handle leaf underflow by borrowing/merge resulting in balanced tree.

Complexity

• Search, insertion, deletion: $O(\log_m N)$ disk accesses (height dependent on block capacity $m$).

Applications of B-Trees

• Database indexes (clustered & secondary) – e.g., MySQL InnoDB, PostgreSQL.
• File systems (NTFS, HFS+, ext4 extents) for directory entries & block maps.
• OS virtual-memory page tables & swap management.
• Router forwarding tables, DNS servers’ zone storage.
• Compiler symbol tables & other on-disk associative structures.

Connections & Real-World Relevance

• AVL (main-memory, pointer-rich) vs. B-Tree (disk/block-oriented). Choice depends on access cost model.
• Asymptotic analysis guides which structure suits workload (search heavy vs. update heavy, memory vs. I/O bound).
• Ethical/Practical: efficient data structures reduce energy and resource usage of large-scale systems.