Unit 1: Introduction and Complexity Analysis

Learning Outcomes

Distinguish a data structure from an abstract data type
Analyse algorithms using Big-O, Omega and Theta notation
Compare best, average and worst case behaviour
Use arrays as the fundamental linear structure

Data Structures and ADTs

A data structure organises data so that it can be accessed and modified efficiently, while an abstract data type specifies the available operations without fixing how they are implemented. Selecting the right structure directly determines a program performance.

Asymptotic Notation

Big-O gives an upper bound on growth, Omega a lower bound and Theta a tight bound. The common complexity classes in increasing order are O(1), O(log n), O(n), O(n log n) and O(n^2).

// O(n): one pass over n elements
for (int i = 0; i < n; i++)
    sum += a[i];

Arrays

An array stores elements in contiguous memory, giving O(1) random access by index, but insertion or deletion in the middle requires shifting elements and costs O(n).

int a[5] = {3, 1, 4, 1, 5};
for (int i = 0; i < 5; i++)
    cout << a[i] << " ";

Summary

This unit defined data structures and ADTs, introduced asymptotic analysis for comparing algorithms, and reviewed the array as the basic contiguous linear structure.

Exercises

State and justify the time complexity of linear search and binary search.
Explain the difference between O(n) and O(n^2) with an example.
Write a function that returns the maximum element of an array.
Give one practical use case each for an array and a linked list.

← Previous Course Home Next →