Introduction to Data Structures and Algorithms: ADT, Types and Complexity

What is a data structure?

A data structure is a way of storing and organising data in memory so that it can be accessed and changed efficiently. The right structure makes an algorithm simple and fast; the wrong one makes it slow. For example, finding a name in a sorted array takes about log₂ n comparisons with binary search, but n comparisons in an unsorted list.

Types of data structures

• Primitive: built into the language: int, float, char, pointers.
• Non-primitive: built from primitive types.
  • Linear: elements form a sequence. Examples: array, stack, queue, linked list.
  • Non-linear: elements form a hierarchy or network. Examples: tree, graph.
• Static: fixed size decided at compile time (array).
• Dynamic: size changes at run time (linked list).

Abstract Data Type (ADT)

An ADT is a logical description of a data type: the values it holds and the operations on them, without saying how they are implemented. It separates what from how.

For example, the Stack ADT has the operations push(x), pop(), peek(), isEmpty() and isFull(). The stack can be implemented with an array or with a linked list; programs using the ADT do not need to know which.

Benefits: abstraction (users see only the interface), encapsulation, and reusability. The implementation can change without changing the programs that use it.

What is an algorithm?

An algorithm is a finite, ordered sequence of well-defined steps that solves a problem. A good algorithm has:

1. Input: zero or more inputs.
2. Output: at least one output.
3. Definiteness: every step is clear and unambiguous.
4. Finiteness: it ends after a finite number of steps.
5. Effectiveness: every step is simple enough to be carried out.

Analysing algorithms

We compare algorithms by how much time (number of basic steps) and space (memory) they need as the input size n grows. We do not measure seconds, because those depend on the computer.

• Worst case: the maximum steps for any input of size n (the usual guarantee).
• Best case: the minimum steps.
• Average case: the expected steps over all inputs.

Asymptotic notations

• Big-O, O(g(n)): an upper bound. f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀.
• Big-Omega, Ω(g(n)): a lower bound. f(n) ≥ c·g(n) for all n ≥ n₀.
• Big-Theta, Θ(g(n)): a tight bound: both O and Ω.

Example: f(n) = 3n² + 5n + 2. For n ≥ 1, f(n) ≤ 3n² + 5n² + 2n² = 10n², so f(n) = O(n²) with c = 10 and n₀ = 1.

Common growth rates

Counting steps: an example

int sum = 0;
for (i = 0; i < n; i++)          /* runs n times        */
    for (j = 0; j < n; j++)      /* runs n times each   */
        sum += a[i][j];          /* n × n = n² steps    */

The inner statement runs n² times, so the time complexity is O(n²). The extra space used is a few variables, O(1).

Exam tip

Questions often ask you to "define ADT with an example" and "explain Big-O notation". Always give the formal definition (f(n) ≤ c·g(n) for n ≥ n₀) and a worked example like the 3n² + 5n + 2 one above.