Data Structures & Algorithms
Complexity • Core Structures • Problem Solving
A concise, original study guide
Original educational guide Page 1
Table of Contents
1. Algorithms and Efficiency
2. Asymptotic Notations
3. Arrays and Searching
4. Sorting
5. Stacks and Queues
6. Linked Lists
7. Trees
8. Graph Algorithms
9. Greedy and Dynamic Programming
10. Exam-Time Complexity Practice
Original educational guide Page 2
1. Algorithms and Efficiency
An algorithm is a finite sequence of well-defined steps that transforms input into a desired output.
Efficiency is commonly studied using time complexity and space complexity. We focus on how resource
usage grows as input size n increases.
2. Asymptotic Notations
Big-O gives an upper growth bound, Big-Omega gives a lower growth bound, and Big-Theta describes a
tight asymptotic bound.
Common growth rates from smaller to larger are O(1), O(log n), O(n), O(n log n), O(n²), O(n³) and O(2■).
3. Arrays and Searching
Array access by index is typically O(1). Linear search checks elements one by one and takes O(n) in the
worst case.
Binary search works on sorted data and repeatedly halves the search interval, giving O(log n) time.
4. Sorting
Bubble sort and insertion sort have O(n²) worst-case time. Insertion sort can perform well on nearly sorted
data.
Merge sort runs in O(n log n) time and uses additional memory. Quicksort has O(n log n) average time but
O(n²) worst-case with poor pivot choices.
5. Stacks and Queues
A stack follows LIFO: last in, first out. Typical operations are push and pop.
A queue follows FIFO: first in, first out. Typical operations are enqueue and dequeue. Both can provide
O(1) operations with suitable implementations.
6. Linked Lists
A linked list stores elements in nodes connected by references. Inserting at a known node can be O(1),
while accessing the kth element requires traversal and is O(n).
7. Trees
A binary tree has at most two children per node. A binary search tree maintains an ordering relationship
between left and right subtrees.
Balanced search trees can provide approximately O(log n) search, insertion and deletion, while an
unbalanced tree may degrade to O(n).
8. Graph Algorithms
Original educational guide Page 3
Graphs contain vertices and edges. Breadth-first search explores level by level and is useful for shortest
paths in unweighted graphs.
Depth-first search explores as far as possible before backtracking. It is useful for connectivity, cycle
detection and traversal.
9. Greedy and Dynamic Programming
Greedy algorithms make the best local choice at each step and are correct only when the problem has the
required greedy property.
Dynamic programming solves overlapping subproblems while storing results. It can turn repeated
exponential work into polynomial-time solutions for suitable problems.
10. Exam-Time Complexity Practice
1) One loop from 1 to n → O(n). 2) Two nested loops each to n → O(n²). 3) Repeatedly halve n → O(log
n). 4) Loop n times with a binary search → O(n log n).
Always identify the dominant operation, count how often it runs, then simplify the growth rate by dropping
constants and lower-order terms.
Original educational guide Page 4