Chapter 1 · Introduction

Data Structures & Algorithm Analysis Self‑paced

Learning Objectives

  • Define data structures and algorithms
  • Classify linear vs. non‑linear structures
  • Distinguish static vs. dynamic memory
  • Explain ADTs and basic operations
  • Analyze time & space complexity
  • Apply Big‑O, Omega, and Theta notations

1. Data Structures Basics

Data structure = a structural representation of the logical relationship between data elements. It organises data to increase process efficiency.

Goals

  • Correctness – works for all valid inputs.
  • Efficiency – fast processing & minimal memory usage.

Basic Operations

  • Traversing – visit each element
  • Searching – locate an item
  • Insertion – add a new element
  • Deletion – remove an element
  • Sorting – arrange in order
  • Merging – combine two structures
Linear: Arrays, Lists, Stacks, Queues Non‑linear: Trees, Graphs ADT: Abstract Data Type (specification vs. implementation)
Which operation involves visiting every element in a data structure?

2. Static vs Dynamic Linear Structures

🔒 Static (Fixed)

Memory allocated at compile‑time. Size cannot change.

C++ int arr[5] = {1,2,3,4,5}; // stack
  • ❌ Wasted memory if underused
  • ❌ Inefficient insertion/deletion (shifting)

🔓 Dynamic (Resizable)

Memory allocated at runtime. Can grow/shrink.

C++ int* dyn = new int[5]{1,2,3,4,5}; // heap (fixed size) std::vector<int> vec = {1,2,3,4,5}; // resizable
  • ✅ Space‑efficient (allocates as needed)
  • ✅ Efficient insertion/deletion (e.g., linked lists, vectors)

Simulate: Static vs Dynamic (click to see the behaviour)

// Output will appear here ...
❓ Which C++ structure is statically allocated on the stack?

3. ADT & Algorithms

Abstract Data Type (ADT) = a collection of data items together with the operations on that data. The implementation is hidden behind a "wall" — the user only sees what it does, not how.

Examples: Array, List, Stack, Queue, Map

Properties of an Algorithm

  • Unambiguous – each step is clear.
  • Input – 0 or more well‑defined inputs.
  • Output – 1 or more outputs.
  • Finiteness – terminates after finite steps.
  • Feasibility – possible with available resources.
  • Independent – language‑agnostic.
Pseudocode Algorithm: Add two numbers 1. START 2. Read a, b 3. c = a + b 4. Print c 5. STOP

4. Complexity Analysis

Time Complexity – how runtime grows with input size n.
Space Complexity – memory usage.

Cases

  • Best – minimum time (e.g., first element found).
  • Average – expected time.
  • Worst – maximum time (the guaranteed upper bound).

Growth Rate Table

ComplexityNameExample
O(1)ConstantAccessing array index
O(log n)LogarithmicBinary search
O(n)LinearFinding in unsorted array
O(n log n)LinearithmicMerge sort
O(n²)QuadraticNested loops
O(2ⁿ)ExponentialTowers of Hanoi
📊 What is the Big‑O of this loop?
for (int i = 1; i <= n; i *= 2) { sum++; }

5. Asymptotic Notations

Big‑O (O)

Upper bound (worst‑case).
\( f(n) \le c \cdot g(n) \) for \( n \ge n_0 \).

Omega (Ω)

Lower bound (best‑case).
\( f(n) \ge c \cdot g(n) \) for \( n \ge n_0 \).

Theta (Θ)

Tight bound (both upper and lower).
\( c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \).

Example: \( f(n) = n^2 + 100n \) → \( O(n^2) \), \( \Omega(n^2) \), and thus \( \Theta(n^2) \).
✏️ For \( f(n) = 4n^3 + 2n^2 + 5 \), the tightest Big‑O is:

6. Chapter Activities (with Solutions)

Attempt each question, then click "Reveal Solution" to check your understanding.

Q1 Asymptotic Notations

Determine Big‑O, Omega, and Theta for:

  1. \( f(n) = 4n^3 + 2n^2 + n + 1 \)
  2. \( g(n) = \log(n^2) \)
  3. \( h(n) = n^2 \cdot \log(n) \)
  4. \( i(n) = 3^n \)
Answers:
1. \( O(n^3), \Omega(n^3), \Theta(n^3) \)
2. \( O(\log n), \Omega(\log n), \Theta(\log n) \)  (since \( \log(n^2)=2\log n \))
3. \( O(n^2\log n), \Omega(n^2\log n), \Theta(n^2\log n) \)
4. \( O(3^n), \Omega(3^n), \Theta(3^n) \) (exponential)

Q2 Growth Rate Functions

Arrange in increasing order of growth rate:

  • \( f(n) = n^2 \)
  • \( g(n) = n \cdot \log n \)
  • \( i(n) = 2^n \)
Order (slowest to fastest): \( n\log n \;<\; n^2 \;<\; 2^n \).
Reason: logarithmic factor grows slower than linear, and exponential dominates polynomial.

Q3 Comparing Algorithms

Algorithm A: \( O(n \log n) \)  |  Algorithm B: \( O(n^2) \).
Which has better asymptotic performance and why?

Answer: Algorithm A is better because \( n \log n \) grows slower than \( n^2 \) for large \( n \). Thus A will run faster on large inputs.

Q4 Runtime of Code Segments

Determine Big‑O for each:

  1. for (int i=0; i<n; i++) cout << i;
  2. for (int i=1; i<=n; i*=2) for (int j=0; j<m; j++) ... (assume m constant)
  3. for (int i=0; i<n; i++) for (int j=0; j<i; j++) sum++;
Answers:
1. \( O(n) \) – linear single loop.
2. \( O(\log n) \) – outer doubles (log n), inner runs constant times.
3. \( O(n^2) \) – inner runs \( 0+1+2+\dots+(n-1) = n(n-1)/2 \), which is quadratic.

Q5 C++ Review: Array/Pointer & Struct/Class

a) Show inserting and traversing 5 integers using an array and a pointer.
b) Create a StudentRecord (ID, name, GPA) and store 5 records, then display them.

a) Array vs Pointer
C++ // Static array int arr[5] = {10,20,30,40,50}; for(int i=0; i<5; i++) cout << arr[i] << " "; // Dynamic pointer (heap) int* ptr = new int[5]{10,20,30,40,50}; for(int i=0; i<5; i++) cout << ptr[i] << " "; delete[] ptr; // free memory
b) Student Record (Struct)
C++ #include <iostream> #include <string> using namespace std; struct Student { int id; string firstName, lastName; double gpa; }; int main() { Student students[5] = { {1,"Alice","Smith",3.8}, {2,"Bob","Johnson",3.2}, {3,"Carol","White",3.9}, {4,"Dave","Brown",2.8}, {5,"Eve","Davis",3.5} }; for(int i=0; i<5; i++) { cout << students[i].id << " " << students[i].firstName << " " << students[i].lastName << " GPA: " << students[i].gpa << endl; } return 0; }
SWEG3103 – Chapter 1  |  Self‑Learning Module  |  2026