Data Structures and Abstract Data Types: An Introduction to Algorithmic Analysis

Abstract Data Types (ADTs) vs. Data Structures

A common point of confusion for students is the difference between an ADT and a data structure. The best way to distinguish them is to think of the ADT as the behavior and the data structure as the storage.

Abstract Data Types (The "What")

An ADT is a theoretical model that defines the logical properties and operations of data without specifying how they are implemented. It sets the rules for what operations are allowed and when they can be performed.

Common fundamental ADTs include:

• Set: A collection of unique elements (e.g., for storing unique usernames).
• Sequence: An ordered collection where position matters (e.g., a sentence of words).
• Dictionary/Map: A collection of unique key-value pairs (e.g., looking up student details via an ID).
• Stack: A Last-In, First-Out (LIFO) structure (e.g., an "undo" function).
• Queue: A First-In, First-Out (FIFO) structure (e.g., a printer queue).
• Priority Queue: Elements are processed based on priority (e.g., hospital triaging).
• Graph/Tree: Representations of complex relationships and hierarchies.

Data Structures (The "How")

Data structures are the concrete implementations of ADTs. They define how data actually sits in a computer's memory. Because different data structures have different physical layouts, they impose limitations on how we can access or manipulate data.

For example, consider the choice between an Array and a Linked List:

• Array: Stores information in a continuous block of memory. This allows for "instant" access to any element via an index, but inserting an element can be expensive because you may need to shift or copy the entire block.
• Linked List: Stores information as a chain of nodes, where each node points to the next. This makes insertions easy (just redirect a few pointers), but finding a specific element requires "hopping" through the list one by one.

Mathematical Modeling of Algorithms

To analyze an algorithm, we must first translate its logic into a mathematical form. We use pseudo-code as a bridge between the logical model and actual code. Depending on the algorithm's structure, we encounter two types of equations:

1. Non-recurrent (Iterative) Algorithms: These use loops to compute answers directly. Their resource usage is often expressed using summations.
2. Recurrent (Recursive) Algorithms: These work by calling themselves on smaller versions of the same problem. Their resource usage is expressed via recurrence equations.

Open-form vs. Closed-form Equations

An open-form equation is one where the number of operations is still tied to the input $n$ (e.g., a summation $\sum_{i=1}^{n} i$). To compare algorithms effectively, we must convert these into closed-form equations, which provide a fixed mathematical expression independent of the summation or recurrence notation.

Once we have a closed-form expression, we identify its asymptotic form—the term that dominates the growth as $n$ becomes very large. This allows us to place the algorithm into a growth class (such as $O(n)$ or $O(n^2)$), enabling a direct comparison between different approaches.

Summary of the Analysis Pipeline

1. Define the basic operation and input size $n$.
2. Create an open-form equation (Summation or Recurrence).
3. Convert to a closed-form equation.
4. Determine the asymptotic form and growth class.

By mastering these connections, you move from simply "writing code" to "designing algorithms" and proving why they are efficient.