Page 1 of 20

Analysis of Algorithms

• Depends on:
  1. Input Size
  2. Input Order

Asymptotic Analysis

• Evaluates the performance (time & space) of an algorithm in terms of input size.
• Shows how the time taken increases as input size increases.

Three Cases

1. Best Case: Lower Bound

2. Worst Case: Upper Bound

3. Average Case: All possible inputs, computing time divided by sum of total number of inputs:

   $$\frac{1}{n+1} \sum_{i=1}^{n+1} O(t_i) \quad \text{(all possible inputs)}$$

Three Notations

1. $O$ Notation (Both bounds)
2. $\Theta$ Notation (Tight bound)
3. $\Omega$ Notation (Lower bound)
4. Little $o$ (Strict upper bound)
5. Little $\omega$ (Strict lower bound)

Diagram: Big O, Theta, and Omega

graph LR
    O["O(g(n))"]
    Theta["Θ(g(n))"]
    Omega["Ω(g(n))"]
    f["f(n)"]
    O --> f
    Theta --> f
    Omega --> f

Amortized Analysis

• Used for algorithms where an occasional operation is very slow but most other operations are faster.

  • E.g., Dynamic Table (for Arrays)

• Amortized cost for n operations:

  $$\frac{\log n!}{n}$$

  For $n$ operations:

  $$\frac{1+2+\cdots +n}{n}\approx \frac{}{}$$

---

Page 2 of 20

Space Complexity & Auxiliary Space

• Auxiliary Space: Extra space or temporary space used by an algorithm.
• Space Complexity: Total space taken by the algorithm with input size. Includes both auxiliary space and input space.
  • E.g., Insertion Sort has $O(1)$ space complexity but takes $O(1)$ auxiliary space.

Pseudo-polynomial

• An algorithm whose worst case time complexity depends on numeric value of input (not number of inputs) is called pseudo-polynomial algorithm.
  • E.g., Algorithm depending on the max value of input.

---

Computational Complexity

• P: Set of problems solvable by deterministic Turing machine in polynomial time.
• NP: Set of decision problems solvable by non-deterministic Turing machine in polynomial time.

graph TD
    P["P"]
    NP["NP"]
    P --> NP
    Ambiguous[/"Ambiguous"/]
    P --> Ambiguous

• NP-Complete: A decision problem $L$ is NP-complete if:

  1. $L$ is in NP
  2. Every problem in NP is reducible to $L$ in polynomial time.

• NP-Hard: Problems as hard as the hardest problems in NP (not necessarily in NP themselves).

---

Page 3 of 20

NP, NP-Complete, NP-Hard Visualization

graph TD
    NP_Hard((NP-Hard))
    NP_Complete((NP-Complete))
    NP((NP))
    P((P))
    SAT((SAT))
    ShortestPath((Shortest Path))
    VertexCover((Vertex Cover))
    Turing((Turing Halting Problem))
    P --> NP
    NP --> NP_Complete
    NP_Complete --> NP_Hard
    NP_Complete --> VertexCover
    NP_Complete --> SAT
    NP --> ShortestPath
    NP_Hard --> Turing

• $P \subseteq NP$ (Only considering decision problems.)

---

Decision Problems vs. Optimization Problems

• Note 1: Decision $\geq$ Optimization
• Note 2: Decision is easier than optimization.

---

Reduction

Let $L_1 \rightarrow L_2$:

• Input for $L_1$ $\xrightarrow{\text{Transform}}$ Output for

---

Page 4 of 20

Sorting Algorithms

Selection, Quick, and Heap are unstable.

---

Quick Sort

• Divide & Conquer, many ways to choose pivot:
  • First element
  • Last element
  • Random element
  • Median

quickSort(arr[], low, high)
{
    if (low < high)
    {
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

partition(arr[], low, high)
{
    i = low - 1
    pivot = arr[high]
    for (j = low; j < high; j++)
        if (arr[j] <= pivot)
            i++
            swap(arr[i], arr[j])
    swap(arr[i+1], arr[high])
    return (i+1)
}

---

Time Complexity

$$T(n) = T(k) + T(n-k-1) + O(n)$$

• Worst Case: $T(n) = T(n-1) + T(0) + O(n) \implies O(n^2)$

---

Page 5 of 20

Quick Sort: Average Case Derivation

• $C_N = N+1 + \frac{2}{N} \sum_{1 \leq k \leq N} C_{k-1}$

$$NC_N = N C_{N-1} + 2 \sum_{k=1}^N C_{k-1} \tag{1}$$ $$(N-1) C_{N-1} = (N-1)N + 2\sum_{k=1}^{N-1} C_{k-1} \tag{2}$$

• Subtracting (2) from (1):

$$NC_N - (N-1)C_{N-1} = N + 2C_{N-1} + 2N$$ $$N C_N = (N+1)C_{N-1} + 2N$$

---

$$\frac{C_N}{N+1} = \frac{C_{N-1}}{N} + \frac{2}{N+1}$$ $$C_N = C_{N-2} + \frac{2}{N-1} + \frac{2}{N}$$ $$C_N = \sum_{k=2}^N \frac{2}{k}$$ $$C_N \approx (N+1) \ln N$$

---

3-Way Quick Sort / Dutch National Flag

while (low <= high)
{
    if (a[mid] < pivot) swap(a[low++], a[mid++]);
    else if (a[mid] == pivot) mid++;
    else swap(a[mid], a[high--]);
}

---

Page 6 of 20

Merge Sort for Linked List

---

Merge Sort

mergeSort(l, h)
{
    if (low < high)
    {
        int mid = (l + h) / 2
        mergeSort(l, mid)
        mergeSort(mid+1, h)
        merge(l, mid, h)
    }
}

---

• $O(n \log n)$ for all cases.

---

Page 7 of 20

Insertion Sort

flowchart LR
    Start --> ForLoop[for (i=0; i<n; i++)]
    ForLoop --> SetNum[int num=a[i]; int j=i-1;]
    SetNum --> WhileLoop[while (j>=0 && a[j]>a[i])]
    WhileLoop --> Swap[swap(a[j], a[j+1])]
    Swap --> End

for (i=0; i<n; i++)
{
    int num=a[i];
    int j=i-1;
    while (j>=0 && a[j]>a[i])
        swap(a[j], a[j+1]);
}

• $O(n^2)$ Worst
• $O(n)$ Best
• $O(n^2)$ Average

---

Selection Sort

for (i=0; i<n; i++)
{
    int min=i;
    for (j=i+1; j<n; j++)
        if (a[j]<a[min])
            min=j;
    swap(a[min], a[i]);
}

• $O(n^2)$ Worst
• $O(n^2)$ Best
• $O(n^2)$ Average

---

Bubble Sort

for (i=0; i<n; i++)
    for (j=1; j<n; j++)
        if (a[j-1] > a[j])
            swap(a[j-1], a[j]);

• $O(n^2)$ Worst
• $O(n)$ Best
• $O(n^2)$ Average

---

Page 8 of 20

Heap Data Structure (Heap DS)

• Tree-based DS in which tree is a complete binary tree.

  • Max-Heap / Min-Heap

• An array-represented complete binary tree:

  1	2	3	4	5	6	7	8	9	10
  16	14	10	8	7	9	3	2	4	1

graph TD
    A[16]
    B[14] C[10]
    D[8] E[7] F[9] G[3]
    H[2] I[4] J[1]
    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G
    D --> H
    D --> I
    E --> J

• Root = first element (i=1)
• Parent(i) = i/2
• Left(i) = 2i
• Right(i) = 2i+1

---

void heapify(i)
{
    int l = left(i)
    int r = right(i)
    int small = i
    if (l < n && a[l] > a[i])
        small = l;
    if (r < n && a[small] > a[r])
        small = r;
    if (small != i)
    {
        swap(a[i], a[small]);
        heapify(small);
    }
}

---

• Other operations (like insert, delete) can be done by a while loop only.

Heap Sort

• Heapify (create heap), for each $N$, heapify & extract.

---

Page 9 of 20

Time Complexity of Heap Build

• For a height $h$ with $n$ nodes in binary tree, at most:

  $$\left\lceil \frac{n}{2^{h+1}} \right\rceil$$

---

• $\sum_{h=0}^\infty x^h = \frac{1}{1-x}$

---

• Replacing $n$ by $\frac{1}{2} \cdot n \log n$:

  $$\sum _{h=0}^{\mathrm{\infty }}$$

---

Page 10 of 20

Linked List: Pointers

Before studying linked lists, let's study pointers.

POINTERS

• Size of pointer depends on architecture:

  • 8 bytes = 64-bit
  • 2/4 bytes = 16/32-bit

• Variables that store address of other variables:

int a;
int *p;
char c, *pc;
p = &a;
*p = 8;
a = 9;

graph TD
    A[a=5]
    B[p=&a]
    A --> B

Pointer Arithmetic

int *p = &a; // 2002
p + 1;       // 2006
p - 1;       // 1998

$(p-q)$ gives address difference.

• Why strongly typed pointers?
  • Due to referencing.

Mind-Blowing Trick

int a = 1027;
int *p = &a;
p;   // 2002
*a;  // 1027
char *p0 = (char*)p;
p0;  // 2002
*p0; // 3

---

Page 11 of 20

Pointer to Pointer

int x = 5;
int *p = &x;
int **q = &p;
*q = &p;

graph TD
    x[x]
    p[*p]
    q[**q]
    x --> p
    p --> q

---

Pointers & Arrays

• $A = \&A[0]$

  • Address: $\&A[i]$ or $(A+i)$
  • Value: $$ or

int A[] <=> int *A;

Pointer & Multi-dimensional Array

$B[i][j] = *(*(B+i) + j) = * (B + i \times j)$

---

Pointer & Strings

char *s = "Abc";

---

2-D Array in Pointer Form

int a[ ][ ] ;
(a + i \times m) + j

---

Reference Variables in C++

int x = 10;
int &y = x; // alias

• Must be initialized with variable.
• Alternative name for existing variable.

---

Page 12 of 20

Types of Pointers

1. Dangling Pointer: A pointer pointing to a memory location that has been deleted (or freed).
2. Void Pointer: A pointer pointing to some data location in storage, which doesn't have any specific type.
3. Null Pointer: A pointer pointing to nothing.
4. Wild Pointer: A pointer which has not been initialized to anything (not even NULL).
   • Beware of wild pointers!

---

Dynamic Memory Allocation

• Allocated on heap just like global or static variables.

int *p = new int;
int *p = new int[10];
delete p;
delete[] p;

---

Back to Linked List

Floyd's Cycle-Finding Algorithm

• Move one pointer by one, other by two. If they are same at a moment, return true.

---

Page 13 of 20

Two Pointer Technique

• Try everything via two pointers, three pointers, done! You are PRO!

• Detect loop & remove (detect loop, get length)

• Reverse a linked list

• Swap two nodes

---

DMA (Dynamic Memory Allocation) in C

int *p = (int*) malloc(size of required);
int *p = (int*) calloc(no. of blocks, size of block);
int *p = (int*) realloc(p, new-size);
free(p);

---

DMA in C++

new int;
new int[n];
delete p;
delete[] p;

---

Page 14 of 20

Binary Tree

• Hierarchical data structure.

  • E.g., File systems, provides moderate access, insertion, deletion.

• A tree with at most 2 children is called BT (Binary Tree).

---

• Note 1: Maximum number of nodes at level $l$ of binary tree = $2^l - 1$

• Note 2: Maximum number of nodes in BT of height $h$ is $2^h - 1$

---

Handshaking Lemma

• Number of vertices with odd degree is even.

---

Page 15 of 20

Number of Binary Trees with n Nodes

• Unlabeled: $n^{th}$ Catalan number

  $$\sum_{i=1}^n C(h-i) C(i-1) = \text{No. of BSTs}$$

---

DFS vs. BFS in Binary Tree

• (Preorder/Inorder/Postorder) (Level-order)

---

---

Page 16 of 20

Binary Search Trees (BST)

• Inorder traversal produces sorted output.
• We can create BST from preorder, postorder, or inorder.

BST Operations

• Range Search
• Nearest Neighbours
• Insert
• Delete

---

Delete in BST

• If leaf, delete.
• If one child, assume it was never there.
• If two children, swap with its inorder successor and delete current one.

---

Check if BT is BST

• Given each node, a range $(-\infty, \infty)$:

  • Left: $(-\infty, val)$
  • Right: $(val, \infty)$

---

Page 17 of 20

Doubly Linked List

• Doubly linked list

  flowchart LR
      A <--> B <--> C

  • with single pointer:

    flowchart LR
        A --> B --> C

    • A next contains XOR of NULL & address of B
    • B next contains XOR of address of A & address of C

---

Hashing

• Hashing

  • Arrays, LL, Heaps, BSTs are not giving best search, insert & delete.

  • Hash gives (to → for) direct access (table)

    • requires huge size

  • Converts to smaller index (using hash function)

    • efficiently computable
    • uniformly distribute keys

    flowchart TD
      0 --→
      1 --→ [ ]
      2 --→ [ ]--→[ ]
      3 --→
      4 --→

    • separate chaining

• Collisions may occur:

  • Use separate chaining
  • Open addressing

---

Page 18 of 20

Open Addressing Methods

1. Linear probing

   $$\text{index} = \text{hash} \% \text{tableSize}$$ $$\text{index} = (\text{hash} + i) \% \text{tableSize}$$

2. Quadratic probing

---

Notes

• Prime number in modulus
  • Because if data is semi pattern based, e.g., multiples of 10:
    • 10, 20, 30, 40, 50
    • For $P = 20$, the buckets will be 10, 0 only
    • While for $P = 7$: 3, 6, 2, 5, 1

---

Page 19 of 20

Bit Manipulation

• Bit manipulation:

  1. $n \& (n-1)$ = removes rightmost 1
  2. Power of 2: $$n \& (n-1)$$ If it equals to 0 $\rightarrow$ power of 2
  3. Count number of ones:

---

Generate all subsets of $A$ of size $N$:

for(i = 0; i < (1<<N); i++) {
    for(j = 0; j < N; j++) {
        if (i & (1<<j))
            print A[j];
    }
}

---

Page 20 of 20

Advanced Tree Algorithms

1. Reverse Level Order

   • Use queue and stack

     flowchart LR
       Q[Queue] -->|root right| S[Stack]
       Q -->|root left| S

2. Spiral Level Order

   graph TD
     1-->2
     1-->3
     2-->4
     2-->5
     3-->6
     3-->7

   • Use two stacks (ST1, ST2)
   • Traverse levels alternately

3. LCA in BST:

   if (left < root->data && right > root->data)
       return root;

4. LCA in BT:

   if (curr == n || curr == y)
       return curr;
   curr = n || curr = y
   sel = 1
   // if either of 2 sides return curr