What did I do today?

• Did some leetcode stuff
• Watched and Read about Memory Management stuff
• Implemented B-Trees
• Recursion Time Complexity revision

Here are the notes on Recursion

Let's break this down using a binary recursion example:

def binary_recursion(n):
    if n <= 1: return 1
    return binary_recursion(n/2) + binary_recursion(n/2)

Visual Representation of the Recursion Tree

Level 0 (k=0):                     n                  # 2^0 = 1 node
                                /     \
Level 1 (k=1):               n/2     n/2             # 2^1 = 2 nodes
                            /   \    /   \
Level 2 (k=2):           n/4  n/4  n/4  n/4         # 2^2 = 4 nodes
                        /  \  /  \  /  \  /  \
Level 3 (k=3):       n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8  # 2^3 = 8 nodes

Why Nodes at Level k = 2^k?

1. Level 0 (Root):

   • Initial call with input n
   • Number of nodes = 2^0 = 1 ✓

2. Level 1:

   • Each node splits into 2 children
   • Number of nodes = 2^1 = 2 ✓

3. Level 2:

   • Each of the 2 nodes splits into 2 children
   • Number of nodes = 2 * 2 = 2^2 = 4 ✓

4. Level 3:

   • Each of the 4 nodes splits into 2 children
   • Number of nodes = 4 * 2 = 2^3 = 8 ✓

Pattern Formation

1. Each parent node creates exactly 2 children
2. Number of nodes at each level:
   • Level 0: 2^0 = 1
   • Level 1: 2^1 = 2
   • Level 2: 2^2 = 4
   • Level 3: 2^3 = 8
   • Level k: 2^k

Impact on Time Complexity

1. Work at Each Level

Level 0: 1 node does n/1 work
Level 1: 2 nodes do n/2 work each
Level 2: 4 nodes do n/4 work each
Level 3: 8 nodes do n/8 work each

2. Total Work per Level

Level 0: (n/1) * 1 = n
Level 1: (n/2) * 2 = n
Level 2: (n/4) * 4 = n
Level 3: (n/8) * 8 = n

3. Height of Tree

• Input reduces by half at each level
• Starting from n, dividing by 2 until we reach 1
• Height = log₂n

4. Total Time Complexity

• Work per level = n
• Number of levels = log₂n
• Total work = n * log₂n
• Therefore, Time Complexity = O(n log n)

Example with Specific Numbers

Let's say n = 16:

Level 0:                16                 # 2^0 = 1 node
                      /    \
Level 1:            8      8              # 2^1 = 2 nodes
                   / \    / \
Level 2:          4   4  4   4           # 2^2 = 4 nodes
                 /\  /\ /\  /\
Level 3:        2 2 2 2 2 2 2 2          # 2^3 = 8 nodes
               /\ /\ /\ /\ /\ /\ /\ /\
Level 4:      1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  # 2^4 = 16 nodes

Common Interview Questions

1. "What's the maximum number of nodes at any level?"

   • Answer: 2^k where k is the level number

2. "How many total nodes are in the tree?"

   • Answer: 2^(h+1) - 1 where h is height of tree

3. "What's the relationship between input size n and tree height h?"

   • Answer: h = log₂n

Interview Tips

1. Always draw the recursion tree first
2. Count nodes level by level
3. Identify the pattern of growth
4. Calculate total work as:
   • (nodes at level) × (work per node at level)
5. Sum up work across all levels

Common Mistakes to Avoid

1. Forgetting that each level doubles in nodes
2. Confusing work per node with total work per level
3. Not accounting for the base case in height calculation
4. Mixing up level number k with total height h

Practice Exercise

Try drawing recursion trees for:

def triple_recursion(n):
    if n <= 1: return 1
    return (triple_recursion(n/3) + 
            triple_recursion(n/3) + 
            triple_recursion(n/3))

Here nodes at level k = 3^k Can you verify this?