COMP 202 - Midterm Study Guide

The nested loop runs n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²) per call. The recurrence is T(n) = T(n-2) + O(n²). Expanding: T(n) = O(n²) + O((n-2)²) + ... + O(1) = O(n² + (n-2)² + ... ) = O(n³) (sum of n/2 terms each O(n²)).

Answer: O(n³)

Key facts:

• log(n!) = Θ(n log n) (Stirling).
• n^(log n) = 2^((log n)²) grows faster than any polynomial but slower than 2ⁿ.
• (log n)² grows slower than any positive power of n.

Order: (slowest → fastest) (log n)² < n < n log n ≡ log(n!) < n^1.5 < n² < n^(log n) < 2ⁿ

By definition, f(n) ∈ O(g(n)) iff there exist constants c > 0 and n₀ ≥ 0 such that for all n ≥ n₀, f(n) ≤ c · g(n).

Pick g(n) = n². For n ≥ 1: 100n ≤ 100n² and 50 ≤ 50n², so f(n) = 3n² + 100n + 50 ≤ 3n² + 100n² + 50n² = 153n².

Choose c = 153 and n₀ = 1. Then f(n) ≤ 153 · n² for all n ≥ 1. Hence f(n) ∈ O(n²). ∎

Outer loop: runs log₂ n times (i halves each iteration). Inner loop: runs log₂ i times, which for each outer iteration is at most log₂ n. Total work: log n · log n = (log n)².

Answer: O((log n)²)

int nodeHeight(BSTNode n) {
  if (n == null) return 0;
  int lh = nodeHeight(n.left);
  int rh = nodeHeight(n.right);
  return 1 + Math.max(lh, rh);
}

Every node is visited exactly once → O(n) where n is the number of nodes.

Copying the first n−1 elements costs O(n). Recurrence: T(n) = T(n-1) + O(n). Expand: T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2.

Formal proof T(n) ∈ O(n²): choose c = 1, n₀ = 1; then T(n) = n(n+1)/2 ≤ n² for all n ≥ 1.

Answer: O(n²)

int sumPositive(int[] a, int i) {
  if (i >= a.length) return 0;            // base case
  int rest = sumPositive(a, i + 1);       // recursive call
  return (a[i] > 0 ? a[i] : 0) + rest;
}

Call with sumPositive(a, 0). Recurrence: T(n) = T(n-1) + O(1) → O(n).

Two recursive calls of size n/2 and O(n) extra work. Recurrence: T(n) = 2 T(n/2) + O(n). By the Master Theorem (case 2), T(n) = O(n log n).

Intuition: this is the merge-sort recurrence pattern.

int countEven(Node head) {
  if (head == null) return 0;
  int restCount = countEven(head.next);
  return ((head.value % 2 == 0) ? 1 : 0) + restCount;
}

Recurrence T(n) = T(n-1) + O(1) → O(n) time, O(n) space (call stack).

Work at each call: O(n) for the loop plus 2 recursive calls on n−1. T(n) = 2 T(n-1) + O(n).

Expansion: T(n) = n + 2(n-1) + 4(n-2) + ... + 2ⁿ·0 ≈ 2ⁿ · (constant). More precisely, T(n) = O(2ⁿ) because the 2ⁿ geometric term dominates.

Answer: O(2ⁿ)

void combineDuplicates(Node head) {
  if (head == null) return;
  Node current = head;
  while (current != null &and current.next != null) {
    if (current.value == current.next.value) {
      current.value = current.value + current.next.value;
      current.next = current.next.next;     // skip the duplicate
      // stay on current - we may need to merge another duplicate
    } else {
      current = current.next;               // advance
    }
  }
}

Each node is visited at most once (either merged and removed, or advanced past). O(n).

Node reverse(Node head) {
  Node prev = null;
  Node curr = head;
  while (curr != null) {
    Node nxt = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nxt;
  }
  return prev;       // new head
}

Time: O(n) - one pass. Space: O(1) - constant extra pointers, in-place.

boolean hasCycle(Node head) {
  Node slow = head, fast = head;
  while (fast != null &and fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
  }
  return false;
}

Time: O(n) - if a cycle exists, fast catches up to slow within one cycle length after slow enters the cycle. Space: O(1).

boolean isPalindrome(Node head, Node tail) {
  Node left = head, right = tail;
  while (left != null &and right != null &and left != right) {
    if (left.value != right.value) return false;
    if (left.next == right) return true;     // adjacent - even length done
    left = left.next;
    right = right.prev;
  }
  return true;
}

Time: O(n) - pointers meet in the middle after n/2 steps. Space: O(1).

Use a HashMap<value, count> to first count occurrences, then traverse again removing duplicates.

Node removeAllDuplicates(Node head) {
  Map<Integer, Integer> count = new HashMap<>();
  for (Node c = head; c != null; c = c.next)
    count.merge(c.value, 1, Integer::sum);

  // dummy head to simplify deletion of first node
  Node dummy = new Node(0); dummy.next = head;
  Node prev = dummy;
  for (Node c = head; c != null; c = c.next) {
    if (count.get(c.value) > 1) prev.next = c.next;
    else                         prev = c;
  }
  return dummy.next;
}

Two passes → O(n) expected time (hashing), O(n) extra space for the map.

Two problems: (1) it destroys the original stack (the original is left empty because pop is destructive); (2) the returned copy is reversed relative to the original - pushing pops in order gives the reverse order.

Stack copyStack(Stack stack) {
  Stack copy = new Stack();
  Stack temp = new Stack();

  // Move everything onto temp (reverses order)
  while (!stack.empty()) temp.push(stack.pop());

  // Pour temp back into both stack (restore) and copy (second reversal)
  while (!temp.empty()) {
    Object v = temp.pop();
    stack.push(v);
    copy.push(v);
  }
  // Now copy is reversed vs stack; reverse once more via temp:
  while (!copy.empty()) temp.push(copy.pop());
  while (!temp.empty()) copy.push(temp.pop());
  return copy;
}

Alternatively, pop+push twice gives the correct order. Time: O(n).

expunge(Stack S):
  if S.isEmpty(): return
  Stack S2 = new Stack()
  while not S.isEmpty():
    prev = S.pop()
    while not S.isEmpty() and S.peek() < prev:
      S.pop()
    S2.push(prev)
  while not S2.isEmpty():
    S.push(S2.pop())

Time: O(n) amortized - each element pushed and popped O(1) times across both stacks.

class MyQueue {
  Stack<Integer> in = new Stack<>();
  Stack<Integer> out = new Stack<>();

  void enqueue(int x) { in.push(x); }

  int dequeue() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) out.push(in.pop());
    }
    return out.pop();
  }
}

• enqueue: O(1).
• dequeue: O(n) worst case for a single call (when out is empty and we move everything), but amortized O(1) - each element is moved from in to out exactly once in its lifetime.

sortStack(S):
  Stack temp = new Stack()
  while not S.isEmpty():
    v = S.pop()
    while not temp.isEmpty() and temp.peek() > v:
      S.push(temp.pop())
    temp.push(v)
  while not temp.isEmpty():
    S.push(temp.pop())

Time: O(n²) worst case - each element can cause linear back-and-forth moves (similar to insertion sort).

Balanced-parenthesis checking is inherently LIFO: when you see a closing bracket, you need the most recently opened unmatched bracket. A queue is FIFO, so it cannot efficiently provide the "last opened" item without being emptied into another structure.

The problem is not naturally solvable with a single queue alone. You would need either a stack or two queues to simulate a stack (which defeats the purpose). With a stack:

boolean balanced(String s) {
  Stack<Character> st = new Stack<>();
  Map<Character,Character> match = Map.of(')', '(', ']', '[', '}', '{');
  for (char c : s.toCharArray()) {
    if ("([{".indexOf(c) >= 0) st.push(c);
    else {
      if (st.isEmpty() || st.pop() != match.get(c)) return false;
    }
  }
  return st.isEmpty();
}

Time: O(n).

A pure queue only supports enqueue/dequeue; to reverse the first k elements we need LIFO behavior. You must either use a stack or use recursion (the call stack is an implicit stack):

reverseK(Queue q, int k):
  if k == 0: return
  int front = q.dequeue()
  reverseK(q, k - 1)                   // recurse
  q.enqueue(front)                     // now add back at rear

  // After recursion, enqueue (n - k) items then dequeue them to rotate:
  for i in 1..(q.size() - k):
    q.enqueue(q.dequeue())

Time: O(n), Space: O(k) for recursion - so "O(1) extra space" is impossible in a strict sense because any such solution must store k items somewhere (stack or recursion).

mirror(Node node):
  if node == null: return
  mirror(node.left)
  mirror(node.right)
  Node tmp = node.left
  node.left = node.right
  node.right = tmp

Every node is visited once → O(n) time, O(h) space for recursion where h is tree height.

                 61 (h=5)
                /       \
          32 (h=3)       80 (h=4)
         /       \         /
     17 (h=2)  53(h=1)   69 (h=3)
         \                /    \
        27(h=1)       66(h=1) 75(h=2)
                                  \
                                 78(h=1)

Does not satisfy AVL property (root's left subtree height 3 vs right 4 is fine, but 80's children have heights 3 and 0 - difference > 1).

boolean isBST(Node root) {
  return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
boolean check(Node n, long lo, long hi) {
  if (n == null) return true;
  if (n.key <= lo || n.key >= hi) return false;
  return check(n.left, lo, n.key) &and check(n.right, n.key, hi);
}

Visits each node once → O(n) time, O(h) space.

⚠ Common pitfall: comparing only to direct parent is insufficient; you must pass down valid (lo, hi) bounds.

int count = 0, result = -1;
void kthSmallest(Node root, int k) {
  if (root == null || count >= k) return;
  kthSmallest(root.left, k);
  count++;
  if (count == k) { result = root.key; return; }
  kthSmallest(root.right, k);
}

Time: O(h + k) - we walk down to the smallest, then visit k nodes in order. For a balanced BST this is O(log n + k); for a skewed BST worst case is O(n).

After insertions

            40(h=4)
           /      \
       20(h=3)   60(h=2)
       /    \    /    \
    10(h=2) 30  50    70
     /      (h=1)(h=1)(h=1)
    5       
   (h=1)
     …and 25 hangs off 30? No - 25 < 30 so 25 is left child of 30.

Cleaner ASCII:

                 40
               /    \
             20      60
            /  \    /  \
           10  30  50  70
           /   /
          5  25

Heights (leaf = 1): 5→1, 10→2, 25→1, 30→2, 50→1, 70→1, 60→2, 20→3, 40→4.

Delete 20 using in-order successor (smallest key in the right subtree of 20) = 25. Replace 20's key with 25, then delete 25 from its original position (it was a leaf).

                 40
               /    \
             25      60
            /  \    /  \
           10  30  50  70
           /
          5

Heights unchanged at 40, 60; 25 has height 3 (max child height 2 + 1).

int best = 0;
int height(Node n) {
  if (n == null) return 0;
  int lh = height(n.left);
  int rh = height(n.right);
  best = Math.max(best, lh + rh);      // longest path through n
  return 1 + Math.max(lh, rh);
}
int diameter(Node root) {
  best = 0;
  height(root);
  return best;
}

One post-order traversal → O(n) time, O(h) space.

Final heap:

              1
           /     \
          5       7
         / \    /  \
        8  13 18   11
       / \
      14 10

Array form: [1, 5, 7, 8, 13, 18, 11, 14, 10].

After first delete-min (remove 1, swap 10 to root, down-heap):

              5
           /     \
          8       7
         / \    /  \
        10 13 18   11
       /
      14

After second delete-min (remove 5, swap 14 to root, down-heap):

              7
           /     \
          8      11
         / \    /  \
        10 13 18   14

Array form: [7, 8, 11, 10, 13, 18, 14].

Inserting one-by-one with up-heap (max-heap):

• 50 → [50]
• 20 → [50,20]
• 70 (swap with 50) → [70,20,50]
• 10 → [70,20,50,10]
• 60 (swap with 20) → [70,60,50,10,20]
• 15 → [70,60,50,10,20,15]
• 5 → [70,60,50,10,20,15,5]
• 100 (bubble up: 100>10, swap; 100>60, swap; 100>70, swap) → [100,70,50,60,20,15,5,10]
• 35 (35<60 stop) → [100,70,50,60,20,15,5,10,35]
• 40 (40>20 swap; 40<70 stop) → [100,70,50,60,40,15,5,10,35,20]

Final array: [100, 70, 50, 60, 40, 15, 5, 10, 35, 20]

                    100
                 /        \
              70           50
            /    \        /   \
          60      40     15    5
         /  \    /
        10   35 20

heapify(A):
  for i = (A.length/2 - 1) down to 0:
    downHeap(A, i)

Why O(n)? The cost of downHeap for a node at height h is O(h). In a complete binary tree, the number of nodes at height h is at most ⌈n / 2^(h+1)⌉. Summing: T(n) ≤ n · Σ_{h=0}^{log n} (h / 2^(h+1)). The infinite series Σ h/2^h converges to 2, so T(n) = O(n).

In contrast, inserting one-by-one does n · log n = O(n log n) because each insertion is O(log n).

Yes. Concatenate the two underlying arrays (O(n)) and run bottom-up heapify on the combined array (O(n) by Q6.2). Total O(n).

Contrast: inserting each element of heap B into heap A one-at-a-time costs O(|B| · log(|A|+|B|)) = O(n log n).

• Parent of i: ⌊(i − 1) / 2⌋
• Left child of i: 2i + 1
• Right child of i: 2i + 2

(If root at index 1 instead: parent ⌊i/2⌋, left 2i, right 2i+1.)

Why removeMin is O(log n): we (1) save A[0] as the return value, (2) move the last leaf to the root, and (3) down-heap - which at each step compares with the two children and swaps with the smaller, moving down one level. A complete binary tree has height ⌊log₂ n⌋, so down-heap does O(log n) swaps/comparisons.

The tree cannot be converted without rotations: Red-Black property bounds the ratio of any two sibling heights by 2 (i.e., h_longer ≤ 2 · h_shorter). In the tree from Q2a, node 80's subtree has height 3 while its sibling (32's subtree) has height 3 - ratio OK at root, but at node 80 itself, the left child (69) has height 3 while right child is empty/height 0, violating the rule.

• Insert 30 → single node.
• Insert 20 → left child of 30. Balanced.
• Insert 10 → left-left of 30. Unbalanced at 30 (bf = +2, left-heavy on left child). LL rotation (rotate right around 30):

      20
     /  \
   10    30

• Insert 25 → right of 20's right? Wait: 25 > 20, goes right of 20. But 30 is right of 20. 25 < 30 → 25 becomes left child of 30.

      20
     /  \
   10    30
         /
       25

Balanced.

• Insert 27 → 27 > 20 → right to 30; 27 < 30 → left to 25; 27 > 25 → right of 25.

      20
     /  \
   10    30
         /
       25
         \
         27

Imbalance detected at 30 (bf = +2 at 30: left subtree (rooted 25) height 2, right height 0). Shape is left-right → LR rotation around (25, 27, 30):

      20
     /  \
   10    27
         / \
        25  30

• Insert 40 → right of 30:

      20
     /  \
   10    27
         / \
        25  30
              \
              40

Heights: 40=1, 30=2, 25=1, 27=3, 10=1, 20=4. bf(20) = 1 − 3 = −2. Violation at 20. Shape is right-right (40 is in 20.right.right's right chain) → RR rotation (left-rotate around 20):

      27
     /  \
   20    30
  /  \     \
 10  25    40

Heights now: 27=3, 20=2, 30=2. bf(27) = 0. ✓

• Insert 35 → 35 > 27 right; 35 > 30 right; 35 < 40 left of 40:

      27
     /  \
   20    30
  /  \     \
 10  25    40
           /
         35

Heights: 35=1, 40=2, 30=3. bf(30) = 0 − 2 = −2. Violation at 30. Shape is right-left → RL rotation around (30, 40, 35): first right-rotate around 40, then left-rotate around 30:

After right-rotate around 40:

      27
     /  \
   20    30
  /  \     \
 10  25    35
             \
             40

After left-rotate around 30:

      27
     /  \
   20    35
  /  \   / \
 10  25 30 40

Final tree is balanced at every node (bf = 0 everywhere). ✓

Red-Black tree with n internal nodes satisfies h ≤ 2 log₂(n+1).

• Max height: 2 · log₂(21) ≈ 2 · 4.39 ≈ 8.78, so h ≤ 8. Achieved when red nodes are maximally distributed (alternating red-black on the longest path).
• Min height: ⌈log₂(21)⌉ = 5 (if all nodes black, the tree is perfectly balanced).

Key intuition: black-height from root to any leaf is identical; a red node cannot have a red parent; so the longest path is at most twice the shortest path.

• AVL enforces |h_left − h_right| ≤ 1 everywhere, giving a tighter height bound of ≈ 1.44 log₂(n+2) vs RBT's ≤ 2 log₂(n+1). Searches traverse fewer levels on average.
• Red-Black has looser balance but fewer rotations on insert/delete (at most 2-3 rotations, often zero for delete rebalancing beyond recoloring).
• Prefer AVL when reads (searches) dominate.
• Prefer Red-Black when inserts and deletes are frequent (e.g., java.util.TreeMap uses red-black).

Inserting in sorted order would make a right-skewed BST; AVL rotations fix this.

• After 1, 2: OK.
• After 3: right-skewed at 1 → LL (actually RR) rotation around 1. Tree:

     2
    / \
   1   3

• After 4: balanced (goes right of 3).
• After 5: RR rotation around 3:

     2
    / \
   1   4
      / \
     3   5

• After 6: balanced? 4's right subtree height = 2 (5 and 6), left = 1 (3). bf at 2 = right 3, left 1 → height diff 2 at root 2. Rotate... Actually after inserting 6:

     2
    / \
   1   4
      / \
     3   5
          \
           6

Imbalance at node 5 (height 2 right, 0 left)? Actually no - the imbalance propagates to the root. At node 2: left height 1, right height 3. Shape right-right → RR rotation around root (lift 4 up):

     4
    / \
   2   5
  / \   \
 1   3   6

• After 7: goes right of 6. Tree:

     4
    / \
   2   5
  / \   \
 1   3   6
          \
           7

Imbalance at 5 (bf right 2, left 0). Right-right → RR around 5:

     4
    / \
   2   6
  / \  / \
 1  3 5   7

Perfectly balanced final AVL. ✓

idx: 0  1  2  3  4  5  6  7  8  9  10 11 12
     -  -  29 3  11 -  27 -  8  16 20 14 -

Load factor = 8/13. Same load factor would hold with separate chaining.

Total collisions: 1 + 2 + 1 + 1 + 2 + 3 = 10 collisions.

Final table:

idx: 0  1  2  3  4  5  6  7  8  9  10
     -  -  -  -  4 15 26 17 18 29 40

Load factor α = n / m where n = number of stored elements, m = number of buckets (array slots).

• Separate chaining: expected search time is O(1 + α). Load factor can exceed 1 (more elements than buckets); lists just get longer. Performance degrades linearly with α.
• Linear probing: expected search time is approximately O(1 / (1 − α)). As α → 1, performance degrades catastrophically (clustering). Load factor must stay < 1 (resize needed well before). Common rule: resize at α = 0.5 or 0.75.

With open addressing, a search for key x probes slots starting at h(x). It stops when it either finds x or hits an empty slot. If we simply emptied a slot on delete, a key that originally probed past that slot would later be unfindable (the search would terminate early).

A DEFUNCT/tombstone marker lets search continue probing but tells insert that the slot is reusable.

With separate chaining, deletion simply unlinks a node from the bucket's list - the bucket is still "occupied" conceptually; there's no probe chain that can be broken.

⚠ When resizing an open-addressing table, DEFUNCT entries are not copied over (they're artifacts of prior collisions, not real data).

Probe sequence for x at attempt i: (h₁(x) + i · h₂(x)) mod 7.

Final table:

idx: 0  1  2  3  4  5  6
    35 12 26  - 18 19  -

Collisions: 1 (for 26) + 1 (for 12) = 2 collisions total.

Inserting the i-th item: finding position by binary search is O(log i), but shifting to maintain sorted order is O(i) in the worst case. Total: 1 + 2 + … + n = Θ(n²). O(n²).

• Copying n items: O(n).
• Resizes happen n/c times. On the k-th resize we copy k·c elements. Total copy work: c + 2c + ... + (n/c)·c = c · (n/c)(n/c+1)/2 = O(n²/c).

Since this dominates linear work, total = O(n²/c).

Contrast with doubling: if B doubles on resize, amortized insert is O(1) - total O(n).

Resizes happen when the array becomes full: after inserting 1, 2, 4, 8, …, 2^k items (i.e., when size hits the current capacity). The cost of the k-th resize is 2^k (copying). Sum of resize costs: 1 + 2 + 4 + … + 2^(⌊log n⌋) = 2^(⌊log n⌋+1) − 1 ≤ 2n.

Each append itself also costs O(1). Total work for n appends ≤ n + 2n = O(n). Amortized cost per append = O(1).

With grow-by-c, after inserting n elements the array has been resized n/c times. Work per resize grows linearly (c, 2c, 3c, ...), summing to c · (n/c)² / 2 = Θ(n² / c) → per-insert amortized cost is Θ(n/c), which grows with n.

With doubling, resize costs form a geometric series bounded by 2n, so per-insert amortized cost is O(1), independent of n.

Conclusion: Doubling (geometric growth) is the standard because it makes append amortized O(1).

Halving when ¼ full (rather than ½ full) leaves a buffer to prevent thrashing: after a resize, we need roughly n/2 operations before another resize can happen. This guarantees the amortized cost of both append and remove is O(1).

Naive "halve when ½ full" thrashes: alternating append/remove at the boundary triggers a resize on every operation, giving O(n) amortized cost per op.

• (a) ArrayList - get(i) is O(1) vs O(n) for a linked list.
• (b) DoublyLinkedList - O(1) at both head and tail; ArrayList is O(n) for head operations.
• (c) ArrayList - contiguous memory, better cache locality; linked lists scatter nodes in heap.
• (d) DoublyLinkedList - O(1) if you already have the node pointer; ArrayList would need O(n) shifts.

Newton's method iteratively approximates a root of a differentiable function f(x):

x_{n+1} = x_n − f(x_n) / f'(x_n)

Starting from an initial guess x₀, each iteration uses the tangent line at x_n to estimate where the function crosses zero. Convergence is quadratic near a simple root (number of correct digits roughly doubles each iteration) - much faster than bisection's linear convergence.

No. The derivative has a singularity at zero. For any starting guess h > 0: f'(h) = 1/(2√h), so x₁ = h − √h / (1/(2√h)) = h − 2h = −h. By symmetry x₂ = h, x₃ = −h, ... The iteration oscillates forever between h and −h and never converges.

Two approaches:

1. Apply Newton directly: x_{n+1} = x_n − (5x_n² + 7x_n + 1) / (10x_n + 7).
2. Use the quadratic formula: x = (−7 ± √(49 − 20)) / 10 = −7/10 ± √29 / 10. Then apply Newton's method to compute √29 to n digits.

Both take O(log n) iterations.

f(x) = x³ − 20, f'(x) = 3x². Iteration: x_{n+1} = x_n − (x_n³ − 20) / (3x_n²) = (2x_n³ + 20) / (3x_n²).

• x₀ = 3: f(3) = 7, f'(3) = 27. x₁ = 3 − 7/27 ≈ 2.7407.
• x₁ ≈ 2.7407: x₁³ ≈ 20.582, 3x₁² ≈ 22.534. x₂ ≈ 2.7407 − 0.582/22.534 ≈ 2.7148.
• x₂ ≈ 2.7148: x₂³ ≈ 20.014, 3x₂² ≈ 22.110. x₃ ≈ 2.7148 − 0.014/22.110 ≈ 2.7144.

The true value is ∛20 ≈ 2.71442. After 3 iterations we're within 10⁻⁴.

1. Zero or near-zero derivative: if f'(x_n) = 0, the update formula divides by zero. E.g., applying to f(x) = x² at x₀ = 0 - derivative is zero at the root, causing slow/failed convergence (only linear convergence at a double root).
2. Oscillation / no root nearby: Fall 2022 Q4c's example - the iteration oscillates between h and −h.
3. Divergence due to bad initial guess: For f(x) = arctan(x), choosing |x₀| too large causes the iterates to grow without bound.

Also worth noting: Newton's method assumes f is differentiable and f' is continuous near the root. For f(x) = |x|^(1/3), derivatives explode and the method diverges.

We want a root of f(x) = 1/x − a (root at x = 1/a). Compute f'(x) = −1/x². Newton:

x_{n+1} = x_n − (1/x_n − a) / (−1/x_n²) = x_n + x_n² (1/x_n − a) = x_n (2 − a · x_n).

Update: x_{n+1} = x_n (2 − a · x_n) - only multiplications and one subtraction, no division. Converges quadratically given a good initial guess (typically from a lookup table). Used in floating-point hardware and in GPU reciprocal approximations.

At the current guess x_n, draw the tangent line to the graph of f at the point (x_n, f(x_n)). The tangent has slope f'(x_n). The tangent crosses the x-axis at x_{n+1} = x_n − f(x_n)/f'(x_n). That's one step of Newton.

Quadratic convergence: Taylor-expand f around the true root r: f(x) = f'(r)(x − r) + ½ f''(ξ)(x − r)². Plugging into the update: x_{n+1} − r ≈ f''(r)/(2 f'(r)) · (x_n − r)². The new error is proportional to the square of the old error - each iteration roughly doubles the number of correct digits (provided f'(r) ≠ 0).