AL

19.1 Algorithms

Understanding searching, sorting, abstract data types, and algorithm complexity

Learning Objectives

By the end of this lesson, you will be able to:

  • Show understanding of linear and binary searching methods
  • Write algorithms to implement linear and binary searches
  • Explain the conditions necessary for binary search
  • Describe how binary search performance varies with data size
  • Show understanding of insertion sort and bubble sort methods
  • Write algorithms to implement insertion sort and bubble sort
  • Explain how sorting performance depends on initial data order and size
  • Show understanding of and use Abstract Data Types (ADT)
  • Write algorithms to find, insert, and delete items in various ADTs
  • Show understanding that a graph is an example of an ADT
  • Describe key features of graphs and justify their use
  • Explain how ADTs can be implemented from other ADTs
  • Describe and implement various ADTs from built-in types
  • Compare algorithms using time and memory criteria
  • Use Big O notation to specify time and space complexity

Key Terms

Linear Search

Searching method that checks each item sequentially until target is found

Binary Search

Searching method that repeatedly divides sorted data in half

Insertion Sort

Sorting method that builds sorted array one item at a time

Bubble Sort

Sorting method that repeatedly steps through list, comparing adjacent items

Abstract Data Type (ADT)

Mathematical model for data types defined by behavior from user perspective

Stack

LIFO (Last In First Out) data structure

Queue

FIFO (First In First Out) data structure

Linked List

Linear collection of nodes where each node points to the next

Binary Tree

Hierarchical data structure with each node having at most two children

Dictionary

Collection of key-value pairs with unique keys

Graph

Collection of nodes (vertices) connected by edges

Algorithm Complexity

Measure of resources (time/memory) required by an algorithm

Big O Notation

Mathematical notation describing algorithm complexity in worst-case scenario

Time Complexity

Amount of time an algorithm takes to complete as function of input size

Space Complexity

Amount of memory an algorithm uses as function of input size

19.1.1 Searching Algorithms

Searching algorithms are used to find specific items in a collection of data. Two fundamental searching methods are linear search and binary search.

Linear Search

How Linear Search Works

  • Start at the beginning of the list
  • Compare each item with the target value
  • If a match is found, return the position/index
  • If the end of the list is reached without finding the item, return "not found"
  • Works on both sorted and unsorted data

Real-Life Example

Imagine looking for your friend in a classroom:

  • Start from the first row, first seat
  • Look at each student one by one
  • Continue until you find your friend
  • If you check every seat and don't find them, they're not in class

This is exactly how linear search works!

Linear Search Algorithm (CIE Pseudocode)

FUNCTION linearSearch(list, target)
    FOR i ← 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            RETURN i    // Found at position i
        ENDIF
    NEXT i
    RETURN -1           // Not found
ENDFUNCTION
Explanation: The algorithm checks each element one by one. If it finds the target, it returns the index. If it reaches the end without finding it, returns -1.

Linear Search Simulation

How it works: The red-highlighted element is currently being compared. Linear search checks each element sequentially until it finds the target.

Target:

Binary Search

How Binary Search Works

  • Data must be sorted first
  • Compare target with middle element
  • If target equals middle element, search is complete
  • If target is less than middle, search left half
  • If target is greater than middle, search right half
  • Repeat until found or search space is empty

Real-Life Example

Imagine looking for a word in a dictionary:

  • Open to the middle of the dictionary
  • Compare your word with words on that page
  • If your word comes before, search first half
  • If your word comes after, search second half
  • Repeat until you find the word

This "divide and conquer" approach is binary search!

Conditions for Binary Search

  • Data must be sorted - This is the most important requirement
  • Works only with random access data structures (like arrays)
  • Not suitable for linked lists (no direct access to middle element)
  • More efficient than linear search for large datasets

Binary Search Algorithm (CIE Pseudocode)

FUNCTION binarySearch(list, target)
    low ← 0
    high ← LENGTH(list) - 1
    
    WHILE low ≤ high
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSEIF list[mid] < target THEN
            low ← mid + 1
        ELSE
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN -1   // Not found
ENDFUNCTION
Explanation: The algorithm repeatedly divides the search interval in half. DIV means integer division (e.g., 7 DIV 2 = 3).

Binary Search Performance

The performance of binary search varies according to the number of data items:

  • Time Complexity: O(log n)
  • Best case: O(1) - target is the middle element
  • Worst case: O(log n) - target is at beginning or end
  • Average case: O(log n)
Example:

Searching 1,000,000 items takes only about 20 comparisons with binary search!

Linear vs Binary Search Comparison

Linear Search Binary Search
Works on any data (sorted or unsorted) Requires sorted data
Time Complexity: O(n) Time Complexity: O(log n)
Simple to implement More complex implementation
Good for small datasets Excellent for large datasets
Sequential access Random access required

Binary Search Simulation

How it works: Orange = currently comparing, Red = search space eliminated. Binary search halves the search space each time!

Target:

Activity 1: Search Algorithm Analysis

Given this sorted array: [5, 12, 19, 26, 33, 40, 47, 54, 61, 68]

  1. Trace the steps of linear search looking for value 47
  2. Trace the steps of binary search looking for value 33
  3. How many comparisons does each search require?
  4. What is the maximum number of comparisons needed to find that value 70 is not in the array using binary search?
Solution:
  1. Linear search for 47:
    • Compare 5 (no match)
    • Compare 12 (no match)
    • Compare 19 (no match)
    • Compare 26 (no match)
    • Compare 33 (no match)
    • Compare 40 (no match)
    • Compare 47 (FOUND!)
    • Total: 7 comparisons
  2. Binary search for 33:
    • Middle = index 4 (33) → FOUND!
    • Total: 1 comparison
  3. Comparisons: Linear = 7, Binary = 1
  4. Binary search for 70 (not in array):
    • Compare middle (33) → 70 > 33, search right
    • Compare middle of right (61) → 70 > 61, search right
    • Compare (68) → 70 > 68, search right
    • Search space empty → NOT FOUND
    • Maximum comparisons: 3 (log₂(10) ≈ 3.32, rounded up)

Activity 2: Algorithm Implementation

Write a CIE pseudocode algorithm for:

  1. A modified linear search that counts how many times the target appears in the array
  2. A binary search that works on a descending sorted array (largest to smallest)
Solution:
  1. Modified linear search: 
    FUNCTION countOccurrences(list, target)
    count ← 0
    FOR i ← 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            count ← count + 1
        ENDIF
    NEXT i
    RETURN count
ENDFUNCTION
  2. Binary search for descending array: 
    FUNCTION binarySearchDescending(list, target)
    low ← 0
    high ← LENGTH(list) - 1
    
    WHILE low ≤ high
        mid ← (low + high) DIV 2
        IF list[mid] = target THEN
            RETURN mid
        ELSEIF list[mid] > target THEN
            // Target is smaller, search right half (descending order)
            low ← mid + 1
        ELSE
            // Target is larger, search left half (descending order)
            high ← mid - 1
        ENDIF
    ENDWHILE
    RETURN -1
ENDFUNCTION

Check Your Understanding: Searching Algorithms

Answer
  • [1 mark] Binary search is much faster for large datasets
  • [1 mark] Time complexity is O(log n) compared to O(n) for linear search
  • [Additional] Example: Searching 1 million items takes ~20 comparisons vs 1 million comparisons
Answer
  • [1 mark] The data must be sorted in ascending or descending order
  • [Additional] Binary search won't work on unsorted data because it relies on comparing with the middle element to decide which half to search next
Answer
  • [1 mark] DIV performs integer division
  • [1 mark] It returns the whole number part of division, discarding any remainder
  • [Additional] Example: 7 DIV 2 = 3, 10 DIV 3 = 3
Answer
  • [1 mark] When the data is unsorted and sorting would take more time than searching
  • [1 mark] When working with small datasets where the difference in performance is negligible
  • [Additional] When working with data structures that don't support random access (like linked lists)
Answer
  • [1 mark] Binary search time complexity is O(log n), meaning it grows logarithmically with data size
  • [1 mark] Doubling the data size only adds one more comparison in worst case
  • [Additional] Example: 16 items → 4 comparisons, 32 items → 5 comparisons, 1 million items → 20 comparisons
Answer
FUNCTION linearSearchExists(list, target)
    FOR i ← 0 TO LENGTH(list) - 1
        IF list[i] = target THEN
            RETURN TRUE
        ENDIF
    NEXT i
    RETURN FALSE
ENDFUNCTION
Marking: [1] Correct loop structure, [1] Correct comparison, [1] Correct return values

19.1.2 Sorting Algorithms

Sorting algorithms arrange data in a specific order (usually ascending or descending). Two fundamental sorting methods are insertion sort and bubble sort.

Insertion Sort

How Insertion Sort Works

  • Builds the sorted array one element at a time
  • Takes each element and inserts it into its correct position
  • Like sorting a hand of playing cards
  • Efficient for small datasets or nearly sorted data
  • Time Complexity: O(n²) worst case, O(n) best case

Real-Life Example

Imagine organizing books on a shelf:

  • Start with first book - it's already "sorted"
  • Take second book, compare with first, swap if needed
  • Take third book, compare with first two, insert in correct position
  • Continue until all books are in order

This is exactly how insertion sort works!

Insertion Sort Algorithm (CIE Pseudocode)

FUNCTION insertionSort(list)
    FOR i ← 1 TO LENGTH(list) - 1
        key ← list[i]
        j ← i - 1
        
        // Move elements greater than key one position ahead
        WHILE j ≥ 0 AND list[j] > key
            list[j + 1] ← list[j]
            j ← j - 1
        ENDWHILE
        
        list[j + 1] ← key
    NEXT i
ENDFUNCTION
Explanation: For each element (starting from second), it finds the correct position in the sorted part and inserts it there.

Bubble Sort

How Bubble Sort Works

  • Repeatedly steps through the list
  • Compares adjacent elements and swaps if they're in wrong order
  • Largest elements "bubble up" to the end
  • Simple but inefficient for large lists
  • Time Complexity: O(n²) in worst and average cases

Real-Life Example

Imagine bubbles rising in a glass of soda:

  • Compare first two bubbles, swap if wrong order
  • Compare next two bubbles, swap if needed
  • Continue to end - largest bubble reaches top
  • Repeat process ignoring already sorted elements

Each pass moves the largest unsorted element to its correct position!

Bubble Sort Algorithm (CIE Pseudocode)

FUNCTION bubbleSort(list)
    n ← LENGTH(list)
    FOR i ← 0 TO n - 2
        FOR j ← 0 TO n - i - 2
            IF list[j] > list[j + 1] THEN
                // Swap elements
                temp ← list[j]
                list[j] ← list[j + 1]
                list[j + 1] ← temp
            ENDIF
        NEXT j
    NEXT i
ENDFUNCTION
Explanation: Outer loop controls passes, inner loop compares adjacent elements. After each pass, largest element bubbles to end.

Sorting Performance Factors

The performance of a sorting routine may depend on:

1. Initial Order of Data
  • Insertion sort: O(n) for nearly sorted data, O(n²) for reverse sorted
  • Bubble sort: O(n) for already sorted (with optimization), O(n²) otherwise
  • Some algorithms perform better on certain data patterns
2. Number of Data Items
  • Both algorithms are O(n²) - performance degrades quickly with size
  • For small n (≤ 100), simple sorts are acceptable
  • For large n, more efficient algorithms (like quicksort) are needed

Sorting Algorithms Comparison

Insertion Sort
Bubble Sort

Key differences: Green = sorted elements, Orange = comparing, Red = swapping. Insertion sort builds sorted portion, bubble sort bubbles largest to end.

Insertion Sort vs Bubble Sort

Insertion Sort Bubble Sort
Builds sorted array one element at a time Repeatedly swaps adjacent elements
Efficient for small or nearly sorted data Simple but generally inefficient
Best case: O(n) (already sorted) Best case: O(n) (with optimization)
Worst case: O(n²) (reverse sorted) Worst case: O(n²)
Stable sort (preserves order of equal elements) Stable sort
In-place sorting (requires O(1) extra space) In-place sorting
Good for linked lists Not suitable for linked lists

Activity 3: Sorting Algorithm Trace

Trace the execution of insertion sort and bubble sort on this array:

[64, 34, 25, 12, 22, 11, 90]
  1. Show each pass of insertion sort
  2. Show each pass of bubble sort
  3. Count the total number of comparisons and swaps for each algorithm
  4. Which algorithm performs better on this specific data? Why?
Solution:
  1. Insertion sort trace:
    • Pass 1: [34, 64, 25, 12, 22, 11, 90] (insert 34)
    • Pass 2: [25, 34, 64, 12, 22, 11, 90] (insert 25)
    • Pass 3: [12, 25, 34, 64, 22, 11, 90] (insert 12)
    • Pass 4: [12, 22, 25, 34, 64, 11, 90] (insert 22)
    • Pass 5: [11, 12, 22, 25, 34, 64, 90] (insert 11)
    • Pass 6: [11, 12, 22, 25, 34, 64, 90] (insert 90)
    • Total comparisons: ~15, swaps: ~15
  2. Bubble sort trace:
    • Pass 1: [34, 25, 12, 22, 11, 64, 90] (64 bubbles to position 6)
    • Pass 2: [25, 12, 22, 11, 34, 64, 90] (34 bubbles to position 5)
    • Pass 3: [12, 22, 11, 25, 34, 64, 90] (25 bubbles to position 4)
    • Pass 4: [12, 11, 22, 25, 34, 64, 90] (22 bubbles to position 3)
    • Pass 5: [11, 12, 22, 25, 34, 64, 90] (12 bubbles to position 2)
    • Pass 6: [11, 12, 22, 25, 34, 64, 90] (no swaps, sorted)
    • Total comparisons: 21, swaps: ~12
  3. Counts: Insertion: ~15 comparisons/swaps, Bubble: 21 comparisons, ~12 swaps
  4. Better algorithm: Insertion sort performs slightly better on this data because it requires fewer comparisons. Both are O(n²) but insertion sort has better constant factors.

Activity 4: Optimized Bubble Sort

The basic bubble sort algorithm can be optimized. Write pseudocode for:

  1. Bubble sort with early termination (stops if no swaps in a pass)
  2. Insertion sort that sorts in descending order
  3. Explain how each optimization improves performance
Solution:
  1. Optimized bubble sort: 
    FUNCTION optimizedBubbleSort(list)
    n ← LENGTH(list)
    swapped ← TRUE
    
    WHILE swapped = TRUE
        swapped ← FALSE
        FOR j ← 0 TO n - 2
            IF list[j] > list[j + 1] THEN
                temp ← list[j]
                list[j] ← list[j + 1]
                list[j + 1] ← temp
                swapped ← TRUE
            ENDIF
        NEXT j
        n ← n - 1  // Last element is now sorted
    ENDWHILE
ENDFUNCTION

    Improvement: Stops early if array becomes sorted, reducing unnecessary passes.

  2. Descending insertion sort: 
    FUNCTION insertionSortDescending(list)
    FOR i ← 1 TO LENGTH(list) - 1
        key ← list[i]
        j ← i - 1
        
        // Change comparison operator for descending order
        WHILE j ≥ 0 AND list[j] < key
            list[j + 1] ← list[j]
            j ← j - 1
        ENDWHILE
        
        list[j + 1] ← key
    NEXT i
ENDFUNCTION

    Change: Use list[j] < key instead of list[j] > key for descending order.

  3. Performance improvements:
    • Optimized bubble sort reduces from O(n²) to O(n) for already sorted data
    • Both optimizations maintain O(n²) worst case but improve average/best cases
    • Early termination prevents unnecessary comparisons when data is sorted early

Check Your Understanding: Sorting Algorithms

Answer
  • [1 mark] Insertion sort builds the sorted array one element at a time by inserting each element in its correct position
  • [1 mark] Bubble sort repeatedly swaps adjacent elements to move larger elements to the end
  • [Additional] Insertion sort is generally more efficient, especially for nearly sorted data
Answer
  • [1 mark] Each element only needs to be compared with a few elements before finding its correct position
  • [1 mark] The inner while loop executes very few times (sometimes not at all) for nearly sorted data
  • [Additional] Time complexity becomes O(n) instead of O(n²) for nearly sorted data
Answer
  • [1 mark] A stable sorting algorithm preserves the relative order of equal elements
  • [1 mark] If two elements have the same value, their original order is maintained after sorting
  • [Additional] This is important when sorting by multiple criteria (e.g., sort by grade, then by name)
Answer
  • [1 mark] Already sorted data: insertion sort is O(n), bubble sort (optimized) is O(n)
  • [1 mark] Reverse sorted data: both algorithms are O(n²) worst case
  • [1 mark] Random data: both are O(n²) average case
  • [Additional] Some algorithms (like quicksort) perform poorly on nearly sorted data but well on random data
Answer
PROCEDURE swap(list, i, j)
    temp ← list[i]
    list[i] ← list[j]
    list[j] ← temp
ENDPROCEDURE
Marking: [1] Correct use of temp variable, [1] Correct assignment order
Answer
  • [1 mark] When simplicity is more important than efficiency (teaching/learning purposes)
  • [1 mark] When you know the data is already nearly sorted and you use the optimized version
  • [Additional] Insertion sort is generally preferred in practice due to better performance

19.1.3 Abstract Data Types (ADT)

An Abstract Data Type (ADT) is a mathematical model for data types defined by their behavior (operations) from the user's perspective, independent of implementation.

What is an ADT?

  • Defines what operations can be performed
  • Does not specify how operations are implemented
  • Separates interface from implementation
  • Examples: Stack, Queue, Linked List, Binary Tree, Graph, Dictionary

Real-Life Example

Think of a TV remote control:

  • You know what buttons do (volume, channel, power)
  • You don't need to know how they work internally
  • The remote is an "abstract interface" to the TV
  • Different TV brands can have different internal implementations

ADTs work the same way - define interface, hide implementation!

Stack ADT

Stack Characteristics

  • LIFO - Last In First Out
  • Operations: push (add), pop (remove), peek (view top)
  • Like a stack of plates - add/remove from top only
  • Applications: function call stack, undo operations, expression evaluation
Stack Visualization
Plate 4 (Top)
Plate 3
Plate 2
Plate 1 (Bottom)
Push adds to top, Pop removes from top (LIFO)

Insert into Stack (Push)

PROCEDURE push(stack, item)
    // Add item to top of stack
    stack.append(item)  // Assuming array implementation
ENDPROCEDURE

Delete from Stack (Pop)

FUNCTION pop(stack)
    IF isEmpty(stack) THEN
        RETURN NULL  // Stack underflow
    ELSE
        item ← stack[LENGTH(stack) - 1]
        REMOVE stack[LENGTH(stack) - 1]
        RETURN item
    ENDIF
ENDFUNCTION

Queue ADT

Queue Characteristics

  • FIFO - First In First Out
  • Operations: enqueue (add to rear), dequeue (remove from front)
  • Like a queue of people - first in line gets served first
  • Applications: printer queues, message queues, breadth-first search
Queue Visualization
Front →
Person 1
Person 2
Person 3
← Rear
Enqueue adds to rear, Dequeue removes from front (FIFO)

Insert into Queue (Enqueue)

PROCEDURE enqueue(queue, item)
    // Add item to rear of queue
    queue.append(item)  // Assuming array implementation
ENDPROCEDURE

Delete from Queue (Dequeue)

FUNCTION dequeue(queue)
    IF isEmpty(queue) THEN
        RETURN NULL  // Queue underflow
    ELSE
        item ← queue[0]
        REMOVE queue[0]  // Remove first element
        RETURN item
    ENDIF
ENDFUNCTION

Linked List ADT

Linked List Characteristics

  • Collection of nodes where each node points to next node
  • Dynamic size - can grow/shrink during execution
  • Efficient insertion/deletion at any position
  • Sequential access (unlike random access in arrays)
  • Types: Singly linked, Doubly linked, Circular linked
Linked List Visualization
A
B
C
D
NULL
Each node contains data and pointer to next node

Find in Linked List

FUNCTION findLinkedList(head, target)
    current ← head
    WHILE current ≠ NULL
        IF current.data = target THEN
            RETURN current
        ENDIF
        current ← current.next
    ENDWHILE
    RETURN NULL  // Not found
ENDFUNCTION

Insert into Linked List

PROCEDURE insertLinkedList(head, newData)
    newNode ← Node(newData)
    newNode.next ← head
    head ← newNode
ENDPROCEDURE

This inserts at beginning. Insertion at other positions requires finding the right node first.

Delete from Linked List

PROCEDURE deleteLinkedList(head, target)
    IF head = NULL THEN RETURN
    
    // Case 1: Delete head
    IF head.data = target THEN
        head ← head.next
        RETURN
    ENDIF
    
    // Case 2: Delete middle/end
    current ← head
    WHILE current.next ≠ NULL
        IF current.next.data = target THEN
            current.next ← current.next.next
            RETURN
        ENDIF
        current ← current.next
    ENDWHILE
ENDPROCEDURE

Binary Tree ADT

Binary Tree Characteristics

  • Hierarchical data structure
  • Each node has at most two children: left and right
  • Root node at top, leaf nodes at bottom
  • Applications: File systems, database indexing, expression trees
  • Special types: Binary Search Tree (BST), Heap, AVL Tree
Binary Tree Visualization
Root (10)
Left (5)
(3)
(7)
Right (15)
(12)
(18)

Find in Binary Tree

FUNCTION findBinaryTree(root, target)
    IF root = NULL THEN
        RETURN NULL
    ENDIF
    
    IF root.data = target THEN
        RETURN root
    ENDIF
    
    // Search left subtree
    leftResult ← findBinaryTree(root.left, target)
    IF leftResult ≠ NULL THEN
        RETURN leftResult
    ENDIF
    
    // Search right subtree
    rightResult ← findBinaryTree(root.right, target)
    RETURN rightResult
ENDFUNCTION

Insert into Binary Search Tree

PROCEDURE insertBST(root, newData)
    IF root = NULL THEN
        root ← Node(newData)
    ELSEIF newData < root.data THEN
        insertBST(root.left, newData)
    ELSE
        insertBST(root.right, newData)
    ENDIF
ENDPROCEDURE

For Binary Search Tree (BST): left < root < right

Dictionary ADT

Dictionary Characteristics

  • Collection of key-value pairs
  • Keys are unique (no duplicates)
  • Operations: insert, delete, search by key
  • Also called: Map, Associative Array, Hash Table
  • Applications: Database indexing, symbol tables, caches
Dictionary Example
Key → Value
"name" → "Alice"
"age" → 25
"grade" → "A"
"city" → "London"
Like a real dictionary: word (key) → definition (value)

Graph ADT

Graph Characteristics

  • Collection of nodes (vertices) connected by edges
  • Can be directed or undirected
  • Can have weighted edges
  • Key features: vertices, edges, adjacency, paths, cycles
  • Applications: Social networks, maps, network routing
Graph Example
A
B
C
D
E
Vertices connected by edges. Can represent relationships.

Justifying Graph Use for a Given Situation

When to use a graph ADT:

  • Social networks: Users are vertices, friendships are edges
  • Transportation maps: Cities are vertices, roads are edges
  • Website links: Pages are vertices, hyperlinks are directed edges
  • Dependency graphs: Tasks are vertices, dependencies are edges

Key justification: Use graphs when you need to represent and analyze relationships/connections between entities.

ADT Implementation

ADTs from Other ADTs

ADTs can be implemented from other ADTs or built-in types:

  • Stack from Array: Use array with top pointer
  • Queue from Linked List: Use linked list with head/tail pointers
  • Dictionary from Array of Records: Key-value pairs in array
  • Binary Tree from Records: Nodes with left/right pointers

Built-in Type Implementation

Some ADTs can be implemented directly from built-in types:

  • Stack using Array: Python list with append/pop
  • Queue using List: Python list with append/pop(0)
  • Dictionary using Hash Table: Python dict type
  • Linked List using Classes: Python class with next pointer

Activity 5: ADT Algorithm Design

Design algorithms for the following ADT operations:

  1. Find the size (number of elements) in a linked list
  2. Check if a binary tree is a Binary Search Tree (BST)
  3. Implement a queue using two stacks
  4. Find if there's a path between two vertices in an undirected graph
Solution:
  1. Linked list size: 
    FUNCTION linkedListSize(head)
    count ← 0
    current ← head
    WHILE current ≠ NULL
        count ← count + 1
        current ← current.next
    ENDWHILE
    RETURN count
ENDFUNCTION
  2. Check if BST: 
    FUNCTION isBST(node, min, max)
    IF node = NULL THEN
        RETURN TRUE
    ENDIF
    
    IF node.data ≤ min OR node.data ≥ max THEN
        RETURN FALSE
    ENDIF
    
    RETURN isBST(node.left, min, node.data) AND
           isBST(node.right, node.data, max)
ENDFUNCTION

// Initial call: isBST(root, -∞, +∞)
  3. Queue using two stacks: 
    // Stack1 for enqueue, Stack2 for dequeue
PROCEDURE enqueue(stack1, item)
    push(stack1, item)
ENDPROCEDURE

FUNCTION dequeue(stack1, stack2)
    IF isEmpty(stack2) THEN
        // Transfer all elements from stack1 to stack2
        WHILE NOT isEmpty(stack1)
            push(stack2, pop(stack1))
        ENDWHILE
    ENDIF
    
    IF isEmpty(stack2) THEN
        RETURN NULL  // Queue empty
    ELSE
        RETURN pop(stack2)
    ENDIF
ENDFUNCTION
  4. Graph path finding (simplified): 
    FUNCTION hasPath(graph, start, end, visited)
    IF start = end THEN
        RETURN TRUE
    ENDIF
    
    visited[start] ← TRUE
    
    FOR EACH neighbor IN graph.adjacencyList[start]
        IF NOT visited[neighbor] THEN
            IF hasPath(graph, neighbor, end, visited) THEN
                RETURN TRUE
            ENDIF
        ENDIF
    NEXT neighbor
    
    RETURN FALSE
ENDFUNCTION

Activity 6: ADT Selection Justification

For each scenario, choose the most appropriate ADT and justify your choice:

  1. Implementing an undo feature in a text editor
  2. Storing student records accessed by student ID
  3. Managing processes in a CPU scheduler
  4. Representing friendships in a social network
  5. Storing a hierarchical file system structure
Solution:
  1. Undo feature: STACK - Operations are LIFO (last action undone first), push for each action, pop to undo.
  2. Student records by ID: DICTIONARY - Student ID is unique key, provides fast O(1) lookup by key.
  3. CPU scheduler: QUEUE - Processes should be FIFO (first come first served), enqueue new processes, dequeue for execution.
  4. Social network friendships: GRAPH - Users are vertices, friendships are edges, can analyze connections and find paths between users.
  5. File system: BINARY TREE - Hierarchical structure with parent-child relationships, directories can have subdirectories (children).

Key principle: Choose ADT based on required operations and data relationships.

Check Your Understanding: Abstract Data Types

Answer
  • [1 mark] Mathematical model for data types defined by behavior from user perspective
  • [1 mark] Specifies what operations can be performed, not how they're implemented
  • [1 mark] Separates interface from implementation
  • [Additional] Examples: Stack, Queue, Linked List, Binary Tree, Graph, Dictionary
Answer
LIFO (Last In First Out):
  • Last element added is first removed
  • Example: Stack of plates
  • ADT: Stack
  • Operations: push (add), pop (remove)
FIFO (First In First Out):
  • First element added is first removed
  • Example: Queue of people
  • ADT: Queue
  • Operations: enqueue (add), dequeue (remove)
Answer
  • [1 mark] Maintain two pointers: front (head) and rear (tail)
  • [1 mark] Enqueue: Add new node at rear, update rear pointer
  • [1 mark] Dequeue: Remove node from front, update front pointer
  • [Additional] Linked list allows dynamic size, no fixed capacity like array
Answer
  • [1 mark] Graph defines operations (add vertex, add edge, find path) without specifying implementation
  • [1 mark] Can be implemented in different ways (adjacency matrix, adjacency list)
  • [Additional] Abstract concept of vertices and edges that can model real-world relationships
Answer
FUNCTION findBinaryTree(root, target)
    IF root = NULL THEN
        RETURN NULL
    ENDIF
    
    IF root.data = target THEN
        RETURN root
    ENDIF
    
    leftResult ← findBinaryTree(root.left, target)
    IF leftResult ≠ NULL THEN
        RETURN leftResult
    ENDIF
    
    rightResult ← findBinaryTree(root.right, target)
    RETURN rightResult
ENDFUNCTION
Marking: [1] Base case, [1] Check current node, [1] Recursive search of subtrees
Answer
  • [1 mark] Array of records: Each element is a key-value pair
  • [1 mark] Hash table: Use hash function to map keys to array indices
  • [1 mark] Binary search tree: Store key-value pairs, ordered by key for efficient search
  • [Additional] Built-in types: Python dict, Java HashMap, C++ unordered_map

19.1.4 Algorithm Complexity

Algorithm complexity measures how resources (time and memory) required by an algorithm scale with input size. Different algorithms performing the same task can be compared using these criteria.

Comparison Criteria

  • Time taken to complete task: How runtime grows with input size
  • Memory used: How much memory (space) algorithm requires
  • Worst-case vs Average-case: Different scenarios may have different performance
  • Best-case: Minimum resources needed

Real-Life Example

Imagine two ways to find a book in a library:

  • Method 1: Check every shelf (linear search) - time increases linearly with library size
  • Method 2: Use catalog system (binary search) - time increases logarithmically
  • For small library, difference is small
  • For huge library, Method 2 is much faster

This is algorithm complexity in action!

Big O Notation

What is Big O?

  • Mathematical notation describing algorithm complexity
  • Measures worst-case scenario growth rate
  • Ignores constants and lower-order terms
  • Focuses on how algorithm scales with input size (n)
  • Examples: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)

Common Complexities

O(1) Constant time - same time regardless of input size
O(log n) Logarithmic time - doubles input adds constant time
O(n) Linear time - time proportional to input size
O(n²) Quadratic time - time proportional to square of input

Algorithm Complexities Summary

Algorithm Time Complexity Space Complexity Explanation
Linear Search O(n) O(1) Check each element once
Binary Search O(log n) O(1) Halve search space each time
Insertion Sort O(n²) O(1) Nested loops compare all pairs
Bubble Sort O(n²) O(1) Nested loops, compare/swap adjacent
Stack Operations O(1) O(n) Push/pop at top only
Queue Operations O(1) O(n) Enqueue/dequeue at ends only
Linked List Search O(n) O(n) Traverse nodes sequentially
Binary Tree Search O(log n)* O(n) *For balanced BST, O(n) worst

Time Complexity

Measures how runtime increases with input size:

  • O(1): Access array element by index
  • O(log n): Binary search on sorted array
  • O(n): Linear search, traverse array
  • O(n log n): Efficient sorts (merge sort, quick sort)
  • O(n²): Simple sorts (bubble, insertion)
  • O(2ⁿ): Fibonacci recursive, traveling salesman

Space Complexity

Measures how memory usage increases with input size:

  • O(1): Constant extra space (in-place algorithms)
  • O(n): Linear extra space (copy of input)
  • O(n²): Quadratic space (adjacency matrix for graph)
  • In-place vs Out-of-place: Some algorithms need extra memory, others don't
  • Auxiliary space: Extra space needed beyond input storage

Complexity Growth Rates Visualization

O(1) - Constant
O(log n) - Logarithmic
O(n) - Linear
O(n log n) - Linearithmic
O(n²) - Quadratic

Growth rates: As input size (n) increases:

  • O(1) stays flat - best
  • O(log n) grows slowly - very good
  • O(n) grows linearly - acceptable
  • O(n log n) grows faster but manageable
  • O(n²) grows quickly - poor for large n
  • O(2ⁿ) grows extremely fast - impractical for large n

Calculating Big O Notation

Rules for determining Big O:

  • Ignore constants: O(5n) = O(n), O(3n² + 2n + 1) = O(n²)
  • Worst-case dominates: O(n² + n log n) = O(n²)
  • Add for sequential statements: O(n) + O(n²) = O(n²)
  • Multiply for nested loops: O(n) × O(n) = O(n²)
  • Different variables: O(n × m) if loops use different input sizes

Activity 7: Complexity Analysis

Analyze the time and space complexity of these algorithms:

  1. Algorithm that finds maximum element in array
  2. Algorithm that finds all pairs of elements in array
  3. Algorithm that recursively calculates factorial
  4. Algorithm that merges two sorted arrays into one sorted array
  5. Explain why O(2n) is the same as O(n) in Big O notation
Solution:
  1. Find maximum: Time: O(n) - check each element once; Space: O(1) - only need few variables
  2. All pairs: Time: O(n²) - nested loops; Space: O(1) - no extra storage needed
  3. Recursive factorial: Time: O(n) - n recursive calls; Space: O(n) - n stack frames
  4. Merge sorted arrays: Time: O(n+m) - linear pass through both; Space: O(n+m) - need result array
  5. O(2n) = O(n): Big O ignores constant factors. It describes growth rate, not exact time. As n→∞, 2n grows at same rate as n (linear). Constants don't change the fundamental scaling behavior.

Activity 8: Algorithm Comparison

Compare these algorithms for searching in different scenarios:

Scenario Data Size Data State
A 100 items Unsorted
B 1,000,000 items Sorted
C 10 items Sorted
D Frequently updated Search rarely
  1. For each scenario, recommend linear or binary search and justify
  2. Estimate worst-case comparisons for each scenario
  3. What other factors besides time complexity might affect choice?
Solution:
  1. Recommendations:
    • A: Linear search - data unsorted, binary search requires sorting first
    • B: Binary search - large sorted dataset, O(log n) much faster than O(n)
    • C: Either works - small dataset, difference negligible; linear simpler
    • D: Linear search - if updates frequent, maintaining sorted order expensive
  2. Worst-case comparisons:
    • A: Linear - 100, Binary - would need sorting first (extra cost)
    • B: Linear - 1,000,000, Binary - ~20 (log₂1,000,000 ≈ 20)
    • C: Linear - 10, Binary - ~4
    • D: Depends on size; linear better if sorting cost > search benefit
  3. Other factors:
    • Memory usage (space complexity)
    • Implementation complexity
    • Data structure limitations (binary needs random access)
    • Frequency of search vs updates
    • Whether data is already sorted

Check Your Understanding: Algorithm Complexity

Answer
  • [1 mark] Worst-case time or space complexity of an algorithm
  • [1 mark] How resource requirements grow as input size increases
  • [Additional] Provides upper bound on growth rate, ignores constants and lower-order terms
Answer
  • [1 mark] O(n²) grows much faster than O(n log n) as n increases
  • [1 mark] For large n, O(n²) algorithms become impractical while O(n log n) remain usable
  • [Additional] Example: n=1,000,000: n²=1 trillion, n log n≈20 million (50× smaller)
Answer
Time Complexity:
  • Measures runtime growth with input size
  • How many operations algorithm performs
  • Examples: O(1), O(n), O(n²)
Space Complexity:
  • Measures memory usage growth
  • How much extra memory algorithm needs
  • Examples: O(1), O(n), O(n²)
Key difference: Time = how fast, Space = how much memory. Some algorithms trade one for the other.
Answer
  • [1 mark] Big O describes growth rate as input size approaches infinity
  • [1 mark] Constants become negligible compared to the growth function for large n
  • [Additional] Focus is on scalability, not exact runtime which depends on hardware/implementation
Answer
FUNCTION exampleAlgorithm(n)
    sum ← 0
    FOR i ← 0 TO n - 1
        FOR j ← 0 TO n - 1
            sum ← sum + 1
        NEXT j
    NEXT i
    
    FOR k ← 0 TO n - 1
        sum ← sum + k
    NEXT k
    
    RETURN sum
ENDFUNCTION
Analysis:
  • First nested loops: O(n × n) = O(n²)
  • Second loop: O(n)
  • Total: O(n² + n) = O(n²) (dominated by n²)
Answer
  • [1 mark] When working with very small input sizes where constants matter more than growth rate
  • [1 mark] When the O(n²) algorithm is simpler to implement/maintain/debug
  • [Additional] When the O(n²) algorithm uses less memory (better space complexity) and memory is constrained

Key Takeaways

  • Linear search checks each element sequentially - O(n) time, works on any data but inefficient for large datasets
  • Binary search requires sorted data - O(log n) time, much faster for large datasets using divide-and-conquer
  • Insertion sort builds sorted array one element at a time - O(n²) worst case, efficient for small/nearly sorted data
  • Bubble sort repeatedly swaps adjacent elements - O(n²), simple but inefficient, good for teaching concepts
  • Abstract Data Types (ADTs) define behavior not implementation - Separate interface from implementation
  • Stack is LIFO - Last In First Out, operations: push/pop
  • Queue is FIFO - First In First Out, operations: enqueue/dequeue
  • Linked list uses nodes with pointers - Dynamic size, efficient insertion/deletion, sequential access
  • Binary tree has hierarchical structure - Each node has at most two children, applications in searching/sorting
  • Dictionary stores key-value pairs - Unique keys, fast lookup by key
  • Graph represents relationships - Vertices and edges, used for networks, maps, dependencies
  • Algorithm complexity measures scalability - Time (operations) and space (memory) requirements
  • Big O notation describes worst-case growth rate - Ignores constants, focuses on behavior as n→∞
  • Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n²) quadratic
  • Choose algorithms based on: Data size, data state (sorted/unsorted), operation frequency, memory constraints

Question Bank

Marking Scheme & Answer
Linear Search:
  • Checks each element sequentially
  • Works on sorted/unsorted data
  • Time Complexity: O(n)
  • Simple implementation
  • Good for small datasets
  • Inefficient for large n
Binary Search:
  • Requires sorted data
  • Divide and conquer approach
  • Time Complexity: O(log n)
  • More complex implementation
  • Excellent for large datasets
  • Needs random access data structure
Key difference: Linear search O(n) vs Binary search O(log n). Binary is exponentially faster for large n but requires sorted data.
Marking Scheme & Answer
FUNCTION insertionSort(list)
    FOR i ← 1 TO LENGTH(list) - 1
        key ← list[i]
        j ← i - 1
        
        // Move elements greater than key one position ahead
        WHILE j ≥ 0 AND list[j] > key
            list[j + 1] ← list[j]
            j ← j - 1
        ENDWHILE
        
        list[j + 1] ← key
    NEXT i
ENDFUNCTION
Explanation of steps:
  1. Outer loop (i): Iterates through each element starting from second
  2. Key: Current element to insert into sorted portion
  3. Inner while loop: Shifts elements greater than key right to make space
  4. Insertion: Places key in correct position in sorted portion
  5. Result: After each iteration, elements [0..i] are sorted
Marking Scheme & Answer
  • [2 marks] Definition: An Abstract Data Type (ADT) is a mathematical model for data types defined by their behavior (operations) from the user's perspective, without specifying implementation details. It separates interface from implementation.
  • [2 marks] Three examples (1 mark for 3 correct):
    1. Stack: LIFO structure with push/pop operations
    2. Queue: FIFO structure with enqueue/dequeue operations
    3. Dictionary: Key-value pairs with insert/delete/search operations
    4. Other examples: Linked List, Binary Tree, Graph
Marking Scheme & Answer
Insert (Push):
PROCEDURE push(stack, item)
    // Add item to top of stack
    stack.append(item)
ENDPROCEDURE

Adds element to top of stack.

Delete (Pop):
FUNCTION pop(stack)
    IF isEmpty(stack) THEN
        RETURN NULL  // Stack underflow
    ELSE
        item ← stack[LENGTH(stack) - 1]
        REMOVE stack[LENGTH(stack) - 1]
        RETURN item
    ENDIF
ENDFUNCTION

Removes and returns top element.

Marking Scheme & Answer
  • [2 marks] Definition: Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends toward infinity. In computer science, it's used to classify algorithms by how their runtime or space requirements grow as input size grows.
  • [3 marks] Examples:
    • O(1): Constant time - accessing array element by index
    • O(log n): Logarithmic - binary search on sorted array
    • O(n): Linear - finding maximum element in array
    • O(n²): Quadratic - bubble sort, insertion sort
    • O(2ⁿ): Exponential - recursive Fibonacci without memoization
  • Key properties: Ignores constants, focuses on worst-case, describes growth rate not exact time.
Marking Scheme & Answer
1. Initial Data Order:
  • Already sorted: Insertion sort O(n), Bubble sort O(n) with optimization
  • Reverse sorted: Both algorithms O(n²) worst case
  • Random order: Both O(n²) average case
  • Nearly sorted: Insertion sort performs well (close to O(n))
2. Number of Data Items:
  • Both algorithms are O(n²) - performance degrades quadratically with size
  • For small n (≤ 100), simple sorts are acceptable
  • For large n, O(n²) becomes impractical
  • More efficient algorithms (O(n log n)) needed for large datasets
Summary: Insertion sort benefits from favorable initial order, while both algorithms suffer with large n due to O(n²) complexity.
Marking Scheme & Answer
FUNCTION findLinkedList(head, target)
    current ← head
    
    WHILE current ≠ NULL
        IF current.data = target THEN
            RETURN current  // Found
        ENDIF
        current ← current.next
    ENDWHILE
    
    RETURN NULL  // Not found
ENDFUNCTION
Explanation:
  • Start at head (first node)
  • Traverse list using next pointers
  • Compare each node's data with target
  • Return node if found, NULL if end reached without finding
  • Time Complexity: O(n), Space Complexity: O(1)
Marking Scheme & Answer
  • [2 marks] Concept: ADTs define interfaces, not implementations. One ADT can be implemented using the operations of another ADT, or using built-in types. This demonstrates abstraction and code reuse.
  • [2 marks] Two examples:
    1. Stack using Array: Use array with top index pointer. Push = add to end, Pop = remove from end.
    2. Queue using Linked List: Use linked list with head (front) and tail (rear) pointers. Enqueue = add to tail, Dequeue = remove from head.
    3. Other examples: Dictionary using Binary Search Tree, Graph using adjacency list (array of linked lists).
Marking Scheme & Answer
Aspect Linear Search Binary Search
Time Complexity O(n) O(log n)
Best Case O(1) - first element O(1) - middle element
Worst Case O(n) - last element or not found O(log n) - not in array
Space Complexity O(1) - in-place O(1) - iterative, O(log n) - recursive
Data Requirement Any order Must be sorted
Efficiency for large n Poor - grows linearly Excellent - grows logarithmically
Key insight: Binary search has better time complexity (O(log n) vs O(n)) but requires sorted data. Both have good space complexity.
Marking Scheme & Answer
  • [1 mark] Social networks involve relationships between users - graphs naturally represent vertices (users) connected by edges (friendships)
  • [1 mark] Graph algorithms can find connections: shortest path between users, mutual friends, friend suggestions
  • [1 mark] Can represent directed/undirected relationships: following (directed) vs mutual friendship (undirected)
  • [Additional] Other graph features useful: weighted edges (relationship strength), clustering coefficients (community detection), centrality measures (influential users)
Alternative ADTs wouldn't work as well: Arrays/lists don't capture relationships, trees assume hierarchy. Graphs provide natural representation of social connections.