Module 1 · Interactive topic

Introduction

Data structures and Big-O

A data structure decides how data is stored — and that decides which operations are fast. To compare them we count steps, not seconds, and ask one question: how does the number of steps grow when the input gets bigger? That answer is written in Big-O.

  • Data structurea way to store and organise data
  • Algorithmstep-by-step instructions
  • Big-Ohow the work grows as the input grows
Count the steps Ready
n 8
steps 0
growth O(n)
  • This step
  • Counted
  • your count on the chart

Ready

Comparisons 0 Shifts 0
Ready

Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

Abstract data type vs data structure

An ABSTRACT DATA TYPE (ADT) says WHAT you can do: a Stack lets you push, pop and peek. A DATA STRUCTURE says HOW it is stored: that stack could live in an array or in a linked list. Same ADT, different structures — and different speeds and memory use. Choosing well is what this track is about.

// ADT: what a Stack can do
push(x)   pop()   peek()   isEmpty()

// Data structure 1: an array + top
int stack[100];  int top = -1;

// Data structure 2: a linked list
struct Node { int data; struct Node *next; };
struct Node *top = NULL;

What is a data structure?

  1. A way to store and organise data in memory.
  2. It comes with operations: insert, delete, search…
  3. Each structure makes some operations fast and others slow.
  4. Examples: array, linked list, stack, queue, tree, graph.

Why do we count steps?

  1. Seconds depend on the computer and the language.
  2. The number of basic steps does not.
  3. So we ask: how do the steps grow as n grows?
  4. n = the size of the input (e.g. array length).

Big-O rules

  1. Keep only the fastest-growing term: n² + n → O(n²).
  2. Drop constant factors: 3n → O(n).
  3. Loops one after another ADD: O(n) + O(n) = O(n).
  4. Loops inside each other MULTIPLY: O(n) × O(n) = O(n²).

Best, average, worst

  1. Best case: the luckiest input (key at index 0).
  2. Worst case: the unluckiest input (key missing).
  3. Average: what you expect on typical input.
  4. Big-O usually describes the WORST case.

Space complexity

  1. Also count the EXTRA memory an algorithm needs.
  2. A few variables → O(1).
  3. A copy of the input → O(n).
  4. Recursion uses stack space for every open call.

How to use this track

  1. Read the short intro, then open the visualizer.
  2. Press Play or step with Next / Previous.
  3. Watch the code line and the counters.
  4. Finish with the practice questions.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 GET-FIRST(A)
2 return A[0] // 1 step for any n
Complexity

How fast is each operation?

How many steps each growth rate needs. A computer doing a billion simple steps per second finishes O(n log n) for n = 1,000,000 in about 0.02 s — O(2ⁿ) for n = 100 would take longer than the age of the universe.

Operation Best Average Worst Speed
O(1) — constant 1 1 1 Instant
O(log n) — logarithmic 3 10 20 Grows with n
O(n) — linear 10 1,000 1,000,000 Grows with n
O(n log n) 33 10,000 20,000,000 Grows with n
O(n²) — quadratic 100 1,000,000 10¹² Grows with n
O(2ⁿ) — exponential 1,024 10³⁰¹ too many Grows with n

Reading the table above

Column Means
Best steps for n = 10
Average steps for n = 1,000
Worst steps for n = 1,000,000

The data structures in this track

Structure Great at Not so good at
Array Reading any index — O(1) Inserting in the middle — O(n)
Linked list Inserting at the front — O(1) Reaching the i-th item — O(n)
Stack / Queue Adding and removing at the ends — O(1) Searching — O(n)
Balanced tree (AVL, B-tree) Search, insert, delete — O(log n) More code and memory per item
Heap Getting the min / max — O(1) Finding any other value — O(n)
Graph Modelling connections (roads, friends) Needs a search (BFS / DFS) to answer questions
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 6 correct
Question 1

What is the difference between an abstract data type and a data structure?

Question 2

A function has one loop that runs n times, followed by another loop that runs n times. What is its Big-O?

Question 3

A loop runs n times, and inside it another loop runs n times. What is its Big-O?

Question 4

What is the Big-O of 3n² + 5n + 100?

Question 5

Which grows the SLOWEST as n gets large?

Question 6

An algorithm stores a copy of its whole input array. What is its space complexity?

Assessment

Introduction quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Back to Data Structures Next topic → Arrays