Data Structures and Algorithms with C · Lecture Notes

Chapter 1: Introduction and Algorithm Analysis

A piece of software goes through a process that runs from writing down requirements to verifying the finished program. The two pillars of that process are data and the algorithm that works on it. These notes first describe the process and the notions of algorithm and abstract data type, and show how an abstract data type is built in C with a header file and an opaque type. They then use selection sort to introduce the first C code, the swap operation, and parameter passing through pointers. Most of the chapter is devoted to computing how much memory and time a program uses: counting program steps, classifying the result with O, Ω, and Θ notation, and comparing growth rates. The magic square problem shows that the right algorithm matters more than the hardware. The last sections cover measuring real running time with clock(), the pitfalls of measurement, and the cost of recursive routines.

Learning outcomes

Know the process
Explain the five phases of the system life cycle and where data structure decisions fall in each.
Abstract
Define algorithm and abstract data type; build an interface in C with a header file and an opaque type.
Count
Derive the memory requirement and the number of program steps of a C routine (sum, rsum, add).
Classify
Express the step count with O, Ω, and Θ; tell the best, average, and worst cases apart.
Compare
Interpret how the common complexity classes separate as n grows.
Measure
Measure running time with clock(); recognize measurement pitfalls such as clock ticks and output operations.

1.1Textbooks and love of the profession

Data structures and algorithms are among the foundation courses on which the rest of computer engineering is built. Every engineer who writes an operating system, a compiler, a database, networking software, or a game engine decides how to keep data in memory and by what method to process it. In this course every structure is implemented in C. Because C exposes memory directly, it lets you see plainly how a structure sits in memory, what a pointer points to, and when allocated memory is given back.

1.1.1Textbooks

The main textbook of the course is Fundamentals of Data Structures in C by Horowitz, Sahni, and Anderson-Freed. The order of topics, the examples, and most of the code in these notes come from the first chapter of that book. The book actually exists in three editions. The code in the first edition was written in a pseudo-language called SPARKS. In later editions the same material was rewritten in C and in C++. The topics and their order are nearly the same; what changes is the language of the code. The C++ edition is the most comprehensive because of its classes and templates, but this course follows the C edition (Figure 1.1).

Fundamentals ofData StructuresSPARKS languageFund. of DataStructures in Ccourse textbookFund. of DataStructures in C++most complete
Figure 1.1: The three editions of the textbook. From left to right: the first edition written in the SPARKS pseudo-language, the C edition, which is the main book of the course, and the most comprehensive C++ edition.

Second on the shelf is Kernighan and Ritchie's The C Programming Language. Dennis Ritchie is the designer of C, and the book describes every detail of the language briefly and precisely. It is the place to look whenever there is doubt about the precedence of an operator, the return value of a standard library function, or the meaning of a declaration. It should therefore stay within reach as a desk reference.

Two more books are recommended as additional sources. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein is known simply as CLRS, after its authors' initials. It is the most mathematically rigorous treatment of asymptotic notation, worst-case and average-case analysis, and amortized analysis. Sedgewick's Algorithms in C presents the same algorithms with C code and a large number of measurements.

1.1.2Loving the profession

Doing a job well depends largely on loving it. An archaeologist lives in the present, but his mind is five thousand five hundred years in the past. Looking at a burial chamber, he can argue about why a pharaoh's wife might have been buried there. An astronomer takes photographs for years to show that a black hole exists, and rejoices when a star moves by one pixel in the image. A football fan travels eight hours, buys a ticket for a hundred and fifty liras, and braves the danger of stones and sticks. Most people find it odd when someone makes the same trip for a scientific conference. In all three examples, what makes people put up with the hardship is their interest in what they do.

Programming is no different. Someone who loves the profession explains things sincerely and gets listened to; nobody listens to someone who does the job carelessly. When writing code, too, you should be able to tell what is happening on every line, as if you were living inside the code. You should know what value a variable holds at that moment, which memory cell a pointer points to, and which iteration a loop is on. The trace tables given next to the code in these notes exist to build exactly this habit. A Chinese proverb says it briefly: the way to be happy for a lifetime is to love your work.

1.2The system life cycle

A large piece of software is not written in one sitting. The road from an idea to a program that runs and can be trusted to be correct consists of successive phases. The whole set of these phases is called the system life cycle. Decisions about data structures and algorithms are made in particular phases of this cycle, so knowing the cycle shows where what you learn in this course fits in a real project.

1.2.1Five phases

Horowitz and Sahni divide the life cycle into five phases (Figure 1.2):

  1. Requirements. Every project begins with specifications that state its purpose. This phase writes down which inputs the programmer will be given and which outputs must be produced. For example, the input of a student records program is student records and grades, and its output is transcripts and grade point averages.
  2. Analysis. The problem is broken into manageable parts. There are two ways to do this: bottom-up and top-down.
  3. Design. The data objects of the problem and the operations on them are determined. The definition of the data objects corresponds to an abstract data type, and the definition of the operations corresponds to an algorithm. Both are independent of the programming language. The more time is spent on design, the fewer errors appear in later phases.
  4. Refinement and coding. Representations for the data objects, that is, concrete data structures, are chosen, and the algorithms are coded on top of those structures. How the data is represented determines how efficient the algorithm will be. The same student list can be kept in an array or in a linked list; the cost of searching and inserting varies with this choice.
  5. Verification. The correctness of the program is shown by proof and testing, and the errors found are removed. Each of these three activities is a research area in its own right.
RequirementsAnalysisDesignRefinementand codingVerificationif an error is found, return to design / coding decisions
Figure 1.2: The five phases of the system life cycle. If verification finds an error, one returns to the design or coding decisions, as the dashed arrow shows.

The dashed arrow in the figure shows that the cycle is not a one-way pipeline. An error found during verification sometimes calls for correcting a single line and sometimes for changing a data structure from scratch. The earlier the phase an error originates in, the more expensive it is to fix. A misunderstanding in the requirements causes far more work than a typo in the code.

1.2.2Analysis: bottom-up and top-down

There are two ways to break up the problem in the analysis phase.

In the bottom-up approach the problem is divided directly into parts, and each part is focused on separately. The modules are seen from the start; the problem is solved module by module, and then the parts are combined. This route is fast for teams that have done a similar project before and know which modules are needed. It is preferred when there is experience with the subject of the project.

In the top-down approach a master plan is made first. One asks what the goal is and what the final product will look like. According to this plan, the problem is divided into subproblems, and the subproblems into smaller pieces. This route takes more time, but the likelihood of backtracking and error is lower. It is preferred when there is no experience with the subject, because the parts are defined knowing their place in the whole.

Example 1.1

Let a student records program be analyzed top-down. At the highest level the program consists of three jobs: record management, grade entry, and reporting. Reporting splits in turn into producing transcripts and computing averages. Computing an average requires finding all the courses of a student and taking a credit-weighted mean. At every level, the parts are defined so that they serve the job one level above. In a bottom-up analysis, by contrast, one directly writes modules such as "add student record", "enter grade", and "compute average", and then joins them with a menu.

1.2.3Postponing design and implementation decisions

The decisions made in the design phase are independent of the language. For example, the fields of the student record (number, name, department, grade list) are decided in this phase. But whether this record will be implemented as an array, a linked list, or a tree can be postponed. Postponing is not laziness but a deliberate choice. As it becomes clearer which operations the program will perform and how often, the most suitable implementation can be chosen better. If records are mostly looked up by number, a sorted array or a search tree is suitable. If insertions and deletions are frequent, a linked list comes to the fore.

The same thought applies to coding itself: the longer coding is delayed, the better a method can be found in the background. Sitting down at the keyboard without thinking about the problem means setting out with the first method that comes to mind, which is often not the best one.

1.2.4Coding and verification

Verification covers four activities.

  • Correctness proofs. The correctness of a program can be proved with mathematical techniques. For a small routine this is possible, but proving a large project from start to finish is almost impossible. The practical way is to use algorithms whose correctness has been proved before; this reduces the chance of errors.
  • Testing. Testing needs working code and test data that covers all the scenarios. Empty input, single-element input, the largest input, sorted and reverse-sorted input, and repeated values are at the top of the list. That the compiler reports no syntax errors and the program gives correct output on one example does not show that the program is correct.
  • Debugging. If a proof or tests reveal an error, it is tracked down by considering the design and coding decisions. A well-documented design makes this job considerably easier.
  • Running time. A program that is correct but runs slowly is also of little value. Correctness and efficiency are separate questions; each must be answered separately.
Common mistake

Thinking "it compiled and ran, so it is correct". A sorting program may give the right result on ten random numbers, yet crash on an empty array or sort incorrectly on repeated values. The test data must cover not only the "ordinary" input but also the edge cases.

1.3Algorithm

In the design phase the operations are defined as an algorithm. This word, which in everyday language means "a way of doing a job", has a precise definition in computer science.

1.3.1Definition and the five criteria

Definition 1.1

An algorithm is a finite sequence of instructions that accomplishes a specific task. Every algorithm satisfies five criteria: input, output, definiteness, finiteness, and effectiveness.

The five criteria are summarized in Table 1.1.

Table 1.1: The five criteria an algorithm must satisfy.
CriterionMeaning
InputZero or more quantities are supplied from outside.
OutputAt least one quantity is produced.
DefinitenessEach instruction is clear and unambiguous.
FinitenessIn every case, it terminates after a finite number of steps.
EffectivenessEach instruction is basic and feasible enough to be carried out with pencil and paper.

Let us take the criteria one at a time. The input criterion allows zero inputs: an algorithm that says "write the first ten primes" takes nothing from outside. The output criterion, on the other hand, demands at least one result; a method that produces nothing has no useful task.

Definiteness requires each instruction to be understood in only one way. The instruction "add 6 or 7 to x" is not definite, because it does not say which one is added. "Multiply the number by a sufficiently large value" is not definite either. A programming language such as C satisfies this criterion automatically: every construct of the language has a defined meaning. In an algorithm written in natural language, however, definiteness needs separate attention.

Finiteness requires the algorithm to stop at some point for every input. The instruction "start at 1, keep doubling the number, stop when the result is negative" never stops in mathematics. Effectiveness requires every instruction to be actually doable. Adding two integers is an effective operation. The instruction "write down all the digits of π" is definite, but it is not effective because it cannot be done in finite time.

1.3.2Algorithm versus computational procedure

The finiteness criterion has an interesting consequence: programs that are not supposed to terminate are not algorithms. An operating system runs as long as the computer stays on; it waits for a task, executes it, and goes back to waiting. Because it never ends, by definition it does not count as an algorithm. Such programs are called computational procedures. The parts inside the operating system, however, such as a routine that reads a file from disk or one that picks the next job among those waiting, are algorithms because they terminate.

An algorithm can be expressed in natural language, as a flowchart, or in a programming language. Natural language is easy to read but has trouble achieving definiteness. A flowchart is illustrative for small algorithms, while for large ones it turns into a tangled drawing. In this course algorithms are written in C. In places, short C-like pseudocode is used to show an idea without going into the details of the code.

1.4Abstract data type

In the design phase, data objects are defined independently of the language. The tool for this definition is the abstract data type. An abstract data type separates what a piece of data "does" from "how it is done". This separation is the common framework of every structure implemented in this course (stack, queue, list, tree, graph).

1.4.1Data type and abstract data type

Consider the type int in C. This type consists of two things: the integers in a certain range, and the operations defined on those integers (+, -, *, /, %, comparisons, assignment). A programmer who uses an int variable does not need to know how many bits the number occupies in memory or with what encoding. Nor does the programmer know how addition is carried out in the processor. Only what the operations do is known. In general, a data type is a collection of objects together with the operations defined on those objects.

Definition 1.2

An abstract data type (ADT) is a data type in which the specification of the objects and operations is separated from the representation of the objects in memory and from the implementation of the operations.

Two notions face each other in this definition.

  • The specification answers the question "WHAT is done?" It gives the names of the operations, the types of their parameters, the type of their results, and what each operation does. A programmer who uses the ADT knows only this.
  • The implementation answers the question "HOW is it done?" It contains the representation of the data in memory (a struct, an array, a linked list) and the code that performs the operations. It is hidden from the user.

The benefit of the separation is concrete. Because the implementation is hidden, it can be changed freely as long as the specification stays the same. A stack written with an array can later be rewritten with a linked list, and not a single line of the program that uses the stack changes. Nor can the user write code that depends on the internals of the implementation, because those internals are not visible. The same ADT can be implemented with several data structures, and the choice can be left to the refinement phase of the life cycle.

The operations of an ADT are grouped by their roles:

  • Constructor operations create a new instance of the type.
  • Transformer operations produce a new value from existing instances.
  • Observer or reporter operations give information about an instance without changing it.

1.4.2Specification of the Fraction ADT

Let us make the notion of an abstract data type concrete with a small but complete example: fractions. A fraction consists of a numerator and a nonzero denominator. Let operations be defined on fractions for creating, adding, testing equality, printing, and deleting. The specification is written in a language-independent notation as follows:

ADT Fraction
  objects: num/den, den ≠ 0
  operations:
    create(n, d)   → Fraction /* constructor */
    add(a, b)      → Fraction /* transformer */
    equal(a, b)    → Boolean  /* observer */
    print(a)                  /* reporter */
    delete(a)

The first line of the specification defines the objects: values consisting of a numerator and a denominator, with the denominator nonzero. The following lines give the operations and the result type of each. create(n, d) is a constructor. add(a, b) is a transformer because it produces a new fraction from two fractions. equal(a, b) is an observer that returns a truth value; print(a) is a reporter that writes the fraction to the screen. delete(a) gives back the resource the fraction occupies. There is not a single word in the specification about how the fraction will be kept in memory, and there does not need to be.

The specification also contains a precondition: the denominator cannot be zero. This condition makes it necessary to decide what the create operation will do when it receives a request with a zero denominator. That question is answered in the implementation.

1.4.3The interface in C: header file and opaque type

C has no notion of a class, but it offers two tools for separating the specification from the implementation: the header file and the incomplete type. A header file (.h) carries type and function declarations and is included into other files with #include. The implementation sits in a separate source file (.c). The interface of the Fraction ADT is the following:

/* fraction.h : interface (WHAT?) */
#ifndef FRACTION_H
#define FRACTION_H
typedef struct fraction Fraction; /* opaque */

Fraction *fraction_create(int num, int den);
Fraction *fraction_add(const Fraction *a,
                       const Fraction *b);
int  fraction_equal(const Fraction *a,
                    const Fraction *b);
void fraction_print(const Fraction *f);
void fraction_delete(Fraction *f);
#endif

The lines of the file work as follows:

  • #ifndef FRACTION_H, #define FRACTION_H, and the final #endif form an include guard. These three lines address the preprocessor. If the file is brought in a second time with #include in the same translation unit, FRACTION_H is already defined, so the content is skipped and the same declarations are not made twice.
  • The line typedef struct fraction Fraction; does two things. First it declares that a structure named struct fraction exists, but does not say what its fields are. Then it gives this structure the short name Fraction. A structure whose fields are unknown is an incomplete type: the compiler does not know its size. Therefore a file that uses fraction.h cannot define a variable of type Fraction or access a field such as f->num. It can only hold a pointer of type Fraction *. A type whose fields are hidden from the user in this way is called an opaque type.
  • The five function declarations correspond to the five operations of the ADT. Fractions are always passed around by pointer. The operations that only read a fraction take parameters of type const Fraction *; this is a promise, checked by the compiler, that the function will not modify the fraction pointed to.

The first part of the implementation contains the fields of the structure and the constructor:

/* fraction.c : implementation (HOW?) */
#include <stdio.h>
#include <stdlib.h>
#include "fraction.h"

struct fraction { int num, den; };

Fraction *fraction_create(int num, int den) {
  Fraction *f;
  if (den == 0) return NULL;
  f = malloc(sizeof *f);
  if (f == NULL) return NULL;
  f->num = num;
  f->den = den;
  return f;
}

The line struct fraction { int num, den; }; completes the structure. Because this line appears only inside fraction.c, the fields are known only in this file. The opaque type approach is C's counterpart of the ADT principle that "the implementation is hidden".

The function fraction_create does the following, line by line:

  1. If the denominator is zero, the fraction cannot be created; the function returns NULL. NULL is the null pointer, which points to no object, and here it means "failure".
  2. The call malloc(sizeof *f) allocates memory of the size of one struct fraction. malloc allocates a block of memory of the requested number of bytes from the heap region and returns the starting address of the block. The expression sizeof *f gives the size of the type that f points to, that is, of struct fraction. Using *f instead of rewriting the type name keeps the size automatically correct if the type of f changes later. sizeof does not evaluate its operand; the expression is safe even though f has not yet received a value.
  3. If no memory is left, malloc returns NULL. This case is checked, and the function returns NULL as well. Without the check, the next line would try to write to the place a null pointer points to, and the program would crash.
  4. The -> in the line f->num = num; is the arrow operator: it accesses a field of the structure the pointer points to. f->num means the same as (*f).num.
  5. Finally the address of the new fraction is returned.

The local variable f of the function disappears when the function returns. But the block allocated with malloc lives on, because a block on the heap stays allocated until it is given back with free. Since the address the function returns points to this block, the caller can use the fraction. The situation would be different if the address of a local variable were returned: once the function's frame is gone, that address becomes invalid.

Common mistake

Not checking the return value of malloc. In small test programs memory almost never runs out and the error stays invisible. But in a program that works with large inputs or stays up for a long time, malloc can return NULL. Unchecked code then crashes with a write such as NULL->num. After every malloc call, the result must be compared with NULL.

1.4.4The rest of the implementation

The rest of fraction.c contains the remaining four operations:

Fraction *fraction_add(const Fraction *a,
                       const Fraction *b) {
  return fraction_create(
      a->num * b->den
        + b->num * a->den,
      a->den * b->den);
}
int fraction_equal(const Fraction *a,
                   const Fraction *b) {
  return a->num * b->den
      == b->num * a->den;
}
void fraction_print(const Fraction *f) {
  printf("%d/%d\n", f->num, f->den);
}
void fraction_delete(Fraction *f) { free(f); }

fraction_add applies the common-denominator formula: a/b + c/d = (a·d + c·b) / (b·d). It does not allocate the result itself but calls fraction_create. That way the denominator check and the memory allocation stay in a single place. Since both denominators are nonzero, their product is nonzero too; fraction_create returns NULL only if memory runs out. The implementation does not reduce the result: the result of 1/2 + 1/2 is 4/4. If reduction is wanted, a line can be added that divides the result by the greatest common divisor; this addition does not change the interface.

fraction_equal tests the equality of two fractions by cross-multiplication: a/b = c/d if and only if a·d = c·b. This method also works on unreduced fractions; 2/4 and 1/2 are found equal. In C a comparison operator yields 1 or 0 of type int; the function therefore returns the result of the comparison directly. The Boolean of the specification is represented in C by this int value.

fraction_print writes the fraction in the form num/den. fraction_delete gives the fraction's block back to the heap with free. free returns a block allocated with malloc to the system. Standard C guarantees that the call free(NULL) does nothing; fraction_delete can therefore be called safely with a null pointer as well.

Common mistake

Working with very large numerators and denominators. Products such as a->num * b->den can exceed the range of int. Signed integer overflow is undefined behavior in C: the result can be an arbitrary value, and the program can behave unexpectedly. The problem does not show in small examples; in an implementation that works with large values one must use long long or reduce the result at every step.

1.4.5Using the interface: contract and ownership

A program that uses fractions knows only the interface:

/* main.c : knows only the interface */
#include "fraction.h"
#include <stddef.h> /* NULL */
int main(void) {
  Fraction *a = fraction_create(1, 2);
  Fraction *b = fraction_create(1, 3);
  Fraction *t = NULL;
  if (a && b) t = fraction_add(a, b);
  if (t) fraction_print(t);  /* 5/6 */
  fraction_delete(a); fraction_delete(b);
  fraction_delete(t);  /* free(NULL) is harmless */
  return 0;
}

main.c includes only fraction.h and the header <stddef.h> for the constant NULL. It does not see the fields of struct fraction. The program consists of three files, and when compiling, the two source files are given together, for example cc fraction.c main.c. The compiler compiles each .c file separately, and the linker binds the calls in main.c to the definitions in fraction.c.

The flow of the program is traced in Table 1.2. The addresses in the table are example values chosen to show where the blocks sit; real addresses may differ on every run.

Table 1.2: Trace of the program main.c (addresses are examples).
LineEventabt
a = fraction_create(1, 2)a block {1, 2} is allocated on the heap0x2000 → 1/2——
b = fraction_create(1, 3)a block {1, 3} is allocated on the heap0x20000x2010 → 1/3—
t = NULLno result yet0x20000x2010NULL
if (a && b)neither is NULL: true0x20000x2010NULL
t = fraction_add(a, b)numerator 1·3 + 1·2 = 5, denominator 2·3 = 6; a new block0x20000x20100x2020 → 5/6
if (t) fraction_print(t)5/6 is printed0x20000x20100x2020
fraction_delete(a); fraction_delete(b); fraction_delete(t)three blocks return to the heapinvalidinvalidinvalid

After the last lines of the program, the variables a, b, and t still carry their old addresses, but those addresses no longer point to a valid object. Such pointers are called dangling pointers. Using them is undefined behavior. Since the program ends immediately, no problem arises here.

Two rules must be written down explicitly in order to use an interface safely.

  • Contract. fraction_create returns NULL if the denominator is zero or memory has run out. The caller is obliged to check this result. The checks if (a && b) and if (t) in main follow from this contract. Without the checks, fraction_add(a, b) might try to read a field of a null pointer.
  • Ownership. Every fraction returned by fraction_create and fraction_add belongs to the caller. When the caller is done with the fraction, it must release it with fraction_delete. A block that is not released stays on the heap until the program ends. Memory that can no longer be reached through any pointer but has not been given back is called a memory leak. A program that creates a fraction on every iteration of a loop and forgets to delete it grows until memory runs out.

The reason t is initialized to NULL is also the ownership rule. If a or b cannot be created, fraction_add is never called and t remains NULL. In that case the call fraction_delete(t) at the end of the program turns into free(NULL) and is harmless. Without an initial value, t could hold an arbitrary address, and the call to free could crash the program.

Common mistake

Trying to write a->num in main.c, or to define a variable such as Fraction f;. Both give compile errors, because for main.c the struct fraction is an incomplete type. This error is not a flaw but the very purpose of the opaque type: the user is forced to work only through the functions in the interface. Another mistake is deleting the same fraction twice. The second free tries to give back a block that is no longer allocated; this is also undefined behavior.

1.5Selection sort

Let us see the notion of an algorithm, and how it is written in C, for the first time on a concrete problem: sorting an array of integers from smallest to largest. Sorting means putting elements into ascending or descending order by their keys. The problem has many solutions. In this section selection sort, one of the easiest to understand, is presented first as an idea, then as pseudocode, and finally as C code. The step-by-step conversion of an idea into code is the usual course of algorithm design.

1.5.1The idea

Let an unsorted array list of n elements be given. Selection sort rests on this idea: find the smallest element in the unsorted part of the array and put it at the front of that part. Then the unsorted part shrinks by one element and the same job is repeated. In the first round the smallest of the whole array settles into list[0], in the second the smallest of the rest into list[1]. In general, in round i the smallest of the range list[i] … list[n-1] is moved to list[i]. In C-like pseudocode the idea is written as follows:

for (i = 0; i < n; i++) {
    examine list[i] .. list[n-1];
    let the smallest integer be list[min];
    swap list[i] and list[min];
}

The second and third lines of this pseudocode are not yet C; expressions such as "examine the range" and "let the smallest element be" are not commands a C compiler would understand. But the idea is clear, and each of these lines is easily translated into C. To find the smallest element, the range is scanned from left to right; the index of the smallest seen so far is kept in a variable min. The swap is done with three assignments.

010113229337414sorted regionunsorted region▲ i▲ minswap
Figure 1.3: An intermediate state of selection sort. The green cells (10, 13) are the sorted region and are in their final places. For i = 2 the smallest element of the unsorted region (29, 37, 14) is 14, at index 4; list[2] and list[4] are swapped.

Figure 1.3 shows the state the algorithm maintains in every round. The array is divided into two regions by a dashed line. The sorted region on the left holds the i smallest elements of the array in order; these elements never move again. The unsorted region on the right holds the remaining elements. Each round grows the sorted region by one element. This holds at the start of every round and is the justification for the algorithm's correctness. After n − 1 rounds the sorted region contains the n − 1 smallest elements; the one element left is the largest, so it already sits in the last cell. The array is sorted.

A written algorithm does not have to be accepted as it is. Understanding it, seeing its weak points, and being able to propose a better one when needed is the level this course aims at. Selection sort will be examined with this eye: how many comparisons does it make, how many swaps, and does a sorted input make its job easier?

1.5.2C implementation

First the main program that uses the sorting function:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 101
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))
void sort(int list[], int n);

int main(void) {
  int i, n, list[MAX_SIZE];
  printf("Enter the array size: ");
  if (scanf("%d", &n) != 1 || n < 1 || n > MAX_SIZE) {
    printf("Invalid n!\n");
    return 1;
  }
  for (i = 0; i < n; i++) list[i] = rand() % 100;
  sort(list, n);
  for (i = 0; i < n; i++) printf("%d ", list[i]);
  return 0;
}

The main program works as follows, line by line:

  • #define MAX_SIZE 101 gives the maximum size of the array as a constant. When the constant is changed, both the size of the array and the bounds check change automatically.
  • #define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t)) is a macro. A macro is a name defined with #define that is replaced as text before compilation. Where SWAP(list[i], list[min], temp) is written, the preprocessor puts the text ((temp) = (list[i]), (list[i]) = (list[min]), (list[min]) = (temp)). The comma operator performs the three assignments in order from left to right.
  • void sort(int list[], int n); is a function declaration (a prototype). Because the definition of sort comes after main, the parameter types and return type of the function are declared to the compiler in advance.
  • scanf("%d", &n) reads the array size from the user. &n is the address of n; scanf writes the value it reads to this address. scanf returns the number of items it read successfully. If the user types a letter instead of a number, a value other than 1 is returned.
  • The condition rejects three cases: the read failed, n < 1, or n > MAX_SIZE. The last check matters. The array list has MAX_SIZE cells; if a larger n were accepted, the loops would write to the memory after the end of the array. C does not check for such overflows.
  • rand() % 100 produces a pseudorandom number between 0 and 99. Because srand is not called, the program produces the same array on every run; this is a convenience so that results can be reproduced.
  • In the call sort(list, n), not the array itself but the address of its first element is passed. The expression list[i] inside sort accesses the memory starting at this address; therefore the changes sort makes to the array change the array in main.

The sorting function is the direct C counterpart of the pseudocode:

void sort(int list[], int n) {
  int i, j, min, temp;
  for (i = 0; i < n - 1; i++) {
    min = i;
    for (j = i + 1; j < n; j++)
      if (list[j] < list[min])
        min = j;
    SWAP(list[i], list[min], temp);
  }
}
  • The outer loop runs from i = 0 to n - 2. In the pseudocode the loop ran n times; the last round is unnecessary, because a one-element range is already sorted. That is why the loop condition is written i < n - 1.
  • min = i; provisionally takes the first element of the range to be the smallest.
  • The inner loop scans the remaining elements of the range from j = i + 1 to n - 1. If list[j] < list[min], a smaller element has been found and min is updated. When the inner loop finishes, min is the index of the smallest element of the range.
  • SWAP(list[i], list[min], temp) moves this element to the front of the range. If min already equals i, the swap exchanges an element with itself; the result does not change, and only three unnecessary assignments are made.

When the program is compiled and run with the input n = 10, it prints the ten randomly generated numbers in sorted order. In the environment in which these notes were prepared, the output was 0 24 34 41 58 62 64 67 69 78. The sequence that rand() produces depends on the C library; on another compiler the numbers come out different, but they are always printed in ascending order.

1.5.3Code trace: {29, 10, 14, 37, 13}

Let us trace the function sort on the five-element array {29, 10, 14, 37, 13}. Table 1.3 gives, for every round, the min value found by the inner loop and the array after the swap.

Table 1.3: Trace of the function sort on the array {29, 10, 14, 37, 13}.
iComparisons of the inner loopminSwapArray
010 < 29 yes (min = 1); 14 < 10 no; 37 < 10 no; 13 < 10 no1list[0] ↔ list[1]{10, 29, 14, 37, 13}
114 < 29 yes (min = 2); 37 < 14 no; 13 < 14 yes (min = 4)4list[1] ↔ list[4]{10, 13, 14, 37, 29}
237 < 14 no; 29 < 14 no2with itself (no change){10, 13, 14, 37, 29}
329 < 37 yes (min = 4)4list[3] ↔ list[4]{10, 13, 14, 29, 37}

In the first round the smallest element, 10, is found at index 1 and exchanged with 29. In the second round the scan first takes 14 and then 13 to be the smallest; 13 is swapped with the 29 at index 1. In the third round 14 is already the smallest of the range; SWAP runs but changes nothing. In the fourth and last round 29 and 37 are exchanged. When the outer loop reaches i = 4, the condition i < n - 1 is false and the function ends. In total 4 + 3 + 2 + 1 = 10 comparisons were made and SWAP was called four times, in three of which two different cells were actually exchanged.

1.5.4Analysis

The number of comparisons selection sort makes does not depend on the values of the input; it depends only on n. In round i the inner loop takes the values j = i + 1, …, n − 1, that is, it makes n − 1 − i comparisons. The sum over all rounds is:

(n − 1) + (n − 2) + … + 1 = n(n − 1) / 2

This sum is the sum of the first n − 1 natural numbers. The formula is verified as follows: write the sum once forwards and once backwards and add term by term; every pair adds up to n and there are n − 1 pairs, so twice the sum is n(n − 1). For n = 5 one gets 5 · 4 / 2 = 10 comparisons, which is the number in the trace table. For n = 1000 about half a million comparisons are needed. Because the number of comparisons grows in proportion to n2, the time of selection sort is O(n2). The notation O(n2) says that for large n the number of steps does not exceed a constant multiple of n2.

The number of swaps, on the other hand, is small: a single SWAP is performed in each round, n − 1 times in total. Hence at most n − 1 swaps take place. If the elements are large records and moving them is expensive, this property makes selection sort attractive. As extra memory the algorithm uses only the variables i, j, min, and temp. The array is sorted in place.

1.5.5A faulty version of sort()

When people try to write selection sort, a commonly seen code is this:

void sort(int list[], int n) {
  int i, j, min, temp;
  for (i = 0; i < n; i++) {
    min = i;
    for (j = 0; j < n; j++)
      if (list[j] > list[min]) {
        min = j;
        SWAP(list[i], list[min], temp);
      }
  }
}

Surprisingly, this code still sorts the array. While preparing these notes, all permutations for n ≤ 7 were tried; the result came out sorted in every one. But the code is not the selection sort of the pseudocode. There are three differences:

  1. The inner loop starts not at j = i + 1 but at j = 0; it scans the whole array in every round.
  2. The condition is >, not <; what is sought is not the smallest but the largest element so far.
  3. The swap is made not once after the inner loop but inside the inner loop, every time the condition is true.

Even though the result is correct, the cost is very different. Table 1.4 gives the numbers of comparisons and swaps that the two versions make on the same inputs. The values were measured by adding counters to the two versions. The swap column counts only the SWAPs in which two different cells were actually exchanged (i ≠ min). The random row was taken from a sample array of one hundred elements generated with rand() % 100; on another random array the swap counts change slightly, while the comparison counts do not.

Table 1.4: Numbers of comparisons and swaps of the faulty version and of selection sort.
InputVersionComparisonsSwaps
{29, 10, 14, 37, 13}faulty257
selection103
100 randomfaulty100002561
selection495094
500, 499, …, 1 (descending)faulty250000124750
selection124750250

The faulty version makes n comparisons in every round and runs n rounds: n2 in total. This is more than twice the n(n − 1)/2 comparisons of selection sort. The real difference is in the swaps. On the descending array of 500 elements the faulty version makes 124,750 swaps; selection sort makes only 250. On a descending array, every swap of selection sort puts two elements into their final places at once. For example, the first swap exchanges 1 and 500. That is why 250 swaps are enough. On this input the number of swaps of the faulty version also equals the number of pairs of elements in reverse order, that is, 500 · 499 / 2 = 124,750.

This example shows an important lesson: a program giving the correct result does not show that it implements the intended algorithm. Algorithm analysis asks, besides the result, what it costs to reach that result. The correct version, that is, the one that starts at j = i + 1 and swaps after the inner loop, is the version used in this chapter.

1.5.6SWAP: macro or function?

Exchanging the values of two variables is called a swap. A swap can be written in two ways in C. The first is the macro used in the program:

#define SWAP(x, y, t) \
        ((t) = (x), (x) = (y), (y) = (t))

int temp;
SWAP(list[i], list[min], temp);

The backslash (\) at the end of the line tells the preprocessor that the macro definition continues on the next line. The advantage of the macro is that it carries no function call cost. The preprocessor puts the macro text in place of the call; at run time there is no call, parameter copying, or return. On the other hand, the temporary variable t must be supplied to the macro from outside; this is why temp is defined separately inside sort.

The second way is a function:

void swap(int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

swap(&list[i], &list[min]);

The parameters of the function are not integers but pointers to integers (int *). In C, parameters are passed by value: the function receives a copy of the value sent. A function written as swap(int x, int y) swaps only its own copies; the variables on the caller's side do not change. That is why not the variables themselves but their addresses are sent: swap(&list[i], &list[min]). Inside the function, the expression *x gives the value at the place x points to. Here * is the dereference operator. The assignment *x = *y writes the value that y points to into the place that x points to.

The advantage of the function is that the compiler does type checking: if swap is given an address that is not an int, the compiler warns. The temporary variable temp is a local variable of the function; the caller does not need to define anything. The function's name is given in lowercase as swap. Had the function also been named SWAP, the preprocessor would try to expand every occurrence of SWAP( as the macro and the two definitions would collide.

The macro has a hidden danger: it evaluates its arguments more than once. When SWAP(a[i++], a[j], t) is written, the preprocessor produces this text:

((t) = (a[i++]), (a[i++]) = (a[j]), (a[j]) = (t))

i++ is executed twice. If a = {10, 20, 30, 40}, i = 0, and j = 3, first t = a[0] = 10 and i rises to 1. Then a[1] = a[3] = 40 is written and i rises to 2. Finally a[3] = 10. The result is {10, 40, 30, 10} and i = 2: no swap has been made, and the value 20 has been lost. Had the same call been made with the function, as swap(&a[i++], &a[j]), i++ would be executed once and a[0] and a[3] would be swapped correctly. These results were verified by compiling and running the example.

Common mistake

Giving the macro an argument with a side effect: SWAP(a[i++], a[j], t), SWAP(x, f(), t), and so on. A macro is not a function; arguments are copied as text and re-evaluated everywhere they appear. Macro arguments must be plain variables or expressions without side effects. This is also why every parameter in the macro definition is wrapped in parentheses: expressions such as SWAP(a[k], b[k + 1], t) are then grouped correctly.

1.5.7swap() in memory, step by step

Let us trace how parameter passing with pointers works in memory, using a small program:

void swap(int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

int main(void) {
  int a = 3, b = 8;
  swap(&a, &b);
  printf("%d %d\n", a, b);
}

When run, the program prints 8 3. To see how this result is reached, let us follow the memory step by step. Every function call opens a stack frame on the call stack. The frame holds the parameters and local variables of that call and disappears when the call ends.

  1. Start. In the frame of main there are a = 3 and b = 8 (Figure 1.4a).
  2. Call. When swap(&a, &b) is called, a new frame is opened for swap. Addresses, not values, are copied into the parameters: x points to a; y points to b. temp has not yet received a value (Figure 1.4b).
  3. int temp = *x; The value at the place x points to, that is 3, is read and written into temp.
  4. *x = *y; The value y points to (8) is written to the place x points to, that is, to a in main. Now a = 8 and b = 8 (Figure 1.5a).
  5. *y = temp; The 3 in temp is written to b, which y points to. The swap has taken place in the variables of main itself (Figure 1.5b).
  6. Return. The frame of swap disappears; x, y, and temp no longer exist. But the change they made stays in the frame of main: a = 8, b = 3 (Figure 1.5c).
frame of main()a3b8
frame of main()a3b8frame of swap()xytemp?
Figure 1.4: Memory before and just after the call swap(&a, &b). (a) In the frame of main, a = 3, b = 8. (b) The frame of swap has been opened; x and y point to a and b respectively.
frame of main()a8b8frame of swap()xytemp3
frame of main()a8b3frame of swap()xytemp3
frame of main()a8b3
Figure 1.5: The last steps of the swap. (a) After *x = *y: a has become 8, and temp holds the old value (3). (b) After *y = temp: b has become 3. (c) swap has returned; its frame is gone, but a = 8, b = 3 remain.

The same trace is given with variable values in Table 1.5. In the table the addresses are chosen as examples: 1000 for a and 1004 for b; an int occupies four bytes.

Table 1.5: Trace of the call swap(&a, &b) (addresses are examples).
Stepa (1000)b (1004)xytemp
before the call38———
call3810001004?
temp = *x38100010043
*x = *y88100010043
*y = temp83100010043
return83———
Common mistake

Writing swap(a, b), that is, sending values instead of addresses. Because the function expects int *, the compiler gives a warning or an error; if the warning is ignored, x points to address 3 and y to address 8, and *x accesses invalid memory. The program most likely crashes. Writing the function as void swap(int x, int y), on the other hand, is a silent error: the program compiles and runs, but the values in main do not change.

1.6Performance analysis

In computing the number of comparisons of selection sort, we found the cost of a program without running it, by looking only at the code. This section generalizes that approach. How much memory and time a program needs is computed as a function of the size of the input.

1.6.1Evaluating a program

To decide whether a program is good, the following questions are asked:

  1. Does it do what is required of it?
  2. Does it work correctly?
  3. Is it documented how to run and use it, comments included?
  4. Does it use functions effectively to produce logical results?
  5. Is the code readable?
  6. Does it use primary and secondary memory effectively?
  7. Is the running time acceptable?

The last two questions are the subject of performance evaluation. The first five are at least as important: a program that is fast but gives wrong results, is undocumented, and is unreadable soon loses its value because it cannot be maintained. But the answers to the first five questions are largely a matter of experience and care. The last two can be answered with numbers.

Performance evaluation is done in two ways.

  • Performance analysis is machine independent. The program is not run; its time and memory requirements are estimated by looking at the code. The result is a complexity function.
  • Performance measurement is machine dependent. The program is run on a particular machine with a particular compiler, and the real running time is measured.

The two ways complement each other. Analysis tells in advance how an algorithm will behave as the input grows. Measurement shows whether this prediction holds on a real machine, and brings out the constants that the analysis ignores.

1.6.2Space complexity

Definition 1.3

The space complexity of a program P is the amount of memory the program needs to complete its work:

S(P) = c + SP(I)

Here c is the fixed part, independent of the size of the input and output; SP(I) is the variable part, which depends on the characteristics of the input I.

The fixed part covers the code of the program, simple variables, fixed-size structures, and constants. This memory is the same whatever the input. The variable part is the memory that changes with the input: arrays whose size is set by the input, the frames opened by recursive calls, blocks allocated by malloc according to the input. The characteristic of the input that affects this part most is usually its size: the number of elements of an array, the number of rows and columns of a matrix. In the analysis only the variable part is of interest, because it is what sets programs apart as the input grows.

Example 1.2

Consider this function, which computes an expression of three numbers:

float abc(float a, float b, float c) {
  return a + b + b * c
         + (a + b - c) / (a + b) + 4.00;
}
/* constant memory only: S_abc(I) = 0 */

The function takes three float parameters and returns a single value. There is no such thing as the size of the input; on every call the same three numbers and the same return address are stored. All the memory is in the fixed part: Sabc(I) = 0. The call abc(1, 2, 3) gives 1 + 2 + 2 · 3 + (1 + 2 − 3)/(1 + 2) + 4 = 13.

A habit about memory use should be acquired from the start: write code as if everything were limited. On today's computers memory looks plentiful, but the same code may run on an embedded system, on a phone, or on a server processing millions of records at once. Memory is not wasted just because there is plenty of it anyway.

1.6.3The memory of sum and rsum

Let us compare two functions that add the elements of an array. sum uses a loop, and rsum uses recursion:

float sum(float list[], int n) {
  float tempsum = 0;
  int i;
  for (i = 0; i < n; i++)
    tempsum += list[i];
  return tempsum;
}

float rsum(float list[], int n) {
  if (n)
    return rsum(list, n - 1) + list[n - 1];
  return 0;
}

Recursion is a function calling itself with a smaller input. rsum(list, n) defines the sum of the first n elements as follows: if n = 0, the sum is 0; otherwise list[n-1] is added to the sum of the first n − 1 elements. The case n = 0, which gives a result directly without calling itself, is called the base case. Because every call reduces n by one, the chain eventually reaches the base case.

Let us find the variable memory of the two functions.

  • To sum, not the elements of the array but the address of its first element is passed. In C an array parameter is really a pointer; float list[] and float *list mean the same thing as a parameter. Therefore, however large the array is, sum stores only one address, one int, and two local variables: Ssum(n) = 0. Had the elements been copied by value, as when an array is passed as a value parameter in Pascal, it would have been Ssum(n) = n.
  • rsum(list, n) is called n + 1 times in all: once each for the values n, n − 1, …, 1, 0. Each call opens a frame on the stack, and these frames live together until the base case is reached. Therefore the variable memory is proportional to n: Srsum(n) ∝ n.
system stackrsum(n=3)list · n · return addr.rsum(n=2)list · n · return addr.rsum(n=1)list · n · return addr.rsum(n=0)list · n · return addr.Each call is one frame:16-bit machine: 2 + 2 + 2 = 6 bytesn = 1000 → at least 6000 bytes64-bit: a frame is typically ≥ 24 bytes
Figure 1.6: The system stack at the deepest moment of the call rsum(list, 3). Four frames sit on top of one another; each stores the pointer list, n, and the return address.

Figure 1.6 shows the contents of one frame: the address of the array (list), the parameter n, and the return address that says where the program continues when the function ends. On the 16-bit machine assumed by the textbook, each of these three values is 2 bytes and a frame takes 6 bytes. For n = 1000, 1001 frames, that is at least 6006 bytes, are needed. On today's 64-bit machines addresses are 8 bytes, and compilers also add alignment and register-saving space to the frame. A frame is typically at least 24 bytes, often more.

This difference has a practical consequence. The memory set aside for the call stack is limited; on Windows the default is around 1 MB. If rsum is called with a very large n, the frames exceed this limit and the program crashes with a stack overflow. In a test made while preparing these notes, rsum gave the correct result for n = 100,000, while for n = 1,000,000 the program crashed. With the same input sum ran without trouble. The exact place of the limit varies with the compiler, the operating system, and the build options.

1.6.4Time complexity and the program step

The time T(P) a program P takes is the sum of the compile time and the run time. Compilation is done once, and the program can be run many times afterwards. So only the run time is of interest; this time is denoted tP.

The run time can be written as the sum of the products of the number of each basic operation the program performs and the time of that operation:

tP(n) = ca·ADD(n) + cs·SUB(n) + cl·LDA(n) + cst·STA(n) + …

Here ADD(n) is the number of additions performed for an input of size n, and ca is the time of one addition. There are terms for subtraction (SUB), loading from memory (LDA), and storing to memory (STA) as well. The formula is exact but impractical. The constants c depend on the compiler, the processor, and the state of the cache, and are hard to know in advance. It is also not clear how many machine instructions a compiler will translate a C statement into.

For this reason time is measured in program steps instead of machine instructions.

Definition 1.4

A program step is a syntactically or semantically meaningful program segment whose running time is independent of the size of the input. The time complexity of a program is the number of program steps it executes as a function of the size of the input.

The crucial point of the definition is the phrase "independent of the size of the input". An assignment such as a = b + c * d; counts as a single step; even though it turns into several machine instructions, its time does not depend on n. A loop cannot be counted as a single step, because how many times it runs depends on n. Each test of the loop is a step, and each execution of each statement in its body is a separate step. Declarations (such as int i;) do no work at run time and so are not counted as steps. The function header and the closing brace are not steps either.

The step count is machine independent, yet it keeps its relation to real time: if the step count doubles, the time also roughly doubles. Although the time of a step varies from machine to machine, this ratio does not.

An extreme example shows why performance matters so much. Suppose the bombing system of a fighter plane is being programmed. If this program finds the target and drops the bomb in 3 seconds, and the opponent's does the same job in 2 seconds, the war has been lost from the start. In real-time systems, in servers processing big data, and in games, a difference of one second is the difference between a useful program and a useless one.

1.6.5Counting steps: sum()

An orderly way to find the step count of a function is the step-count table. In the table, three numbers are written for each statement. s/e (steps per execution) is how many steps one execution of the statement takes. Frequency is how many times the statement is executed. Total is the product of the two. The step count of the function is the sum of the total column. The table for the function sum is given in Table 1.6.

Table 1.6: Step-count table of the function sum.
Statements/eFrequencyTotal
float sum(float list[], int n) {000
float tempsum = 0;111
int i;000
for (i = 0; i < n; i++)1n + 1n + 1
tempsum += list[i];1nn
return tempsum;111
}000
Total2n + 3

The row of the table that needs the most care is the for row. The loop body is executed n times, but the loop condition is tested n + 1 times. For the values i = 0, 1, …, n − 1 the test is true and the body is entered; these account for n tests. When i = n, the test is made once more, comes out false, and the loop ends. This last test is also a step. The assignment line and the return are executed once each. The total is 1 + (n + 1) + n + 1 = 2n + 3 steps.

1.6.6Verifying with a counter

The correctness of the table can be checked by adding a counter to the program. A global variable count starts at zero and is increased by one at every program step:

float sum(float list[], int n) {
  float tempsum = 0; count++;
  int i;
  for (i = 0; i < n; i++) {
    count++;             /* for test */
    tempsum += list[i]; count++;
  }
  count++;  /* last test of for */
  count++;  return tempsum;
}

The counter increments stand in place of the steps in the table: one after the assignment, one at each loop test, one at each execution of the body, one at the last test of the loop, and one at the return. The counter for the loop test is placed at the start of the body, because a test has been made before each entry into the body. To count the exit test, there is a separate increment after the loop.

For list = {3, 1, 4} and n = 3, the trace is given in Table 1.7.

Table 1.7: Trace of the call sum(list, 3) with the counter; list = {3, 1, 4}.
Eventitempsumcount
start——0
tempsum = 0—01
test 0 < 3: true002
tempsum += list[0]033
test 1 < 3: true134
tempsum += list[1]145
test 2 < 3: true246
tempsum += list[2]287
test 3 < 3: false388
return tempsum389

In the end count = 9 = 2 · 3 + 3; the formula in the table is confirmed. The function returns 3 + 1 + 4 = 8. The function with the counter was also run for n = 0, 1, …, 6, and every time the value of count came out equal to 2n + 3.

The code with the counter has one detail worth noticing: after the line float tempsum = 0; count++; comes the declaration int i;. Declaring in the middle of a block was forbidden in C89 and has been allowed since C99. The code must therefore be compiled with C99 or a newer standard.

1.6.7Counting steps: rsum()

The step count of a recursive function is found a little differently: the frequency of each statement is computed from how many times the function is called. rsum(list, n) is called n + 1 times in all. The step-count table is given in Table 1.8.

Table 1.8: Step-count table of the function rsum.
Statements/eFrequencyTotal
float rsum(float list[], int n) {000
if (n)1n + 1n + 1
return rsum(list, n-1) + list[n-1];1nn
return 0;111
}000
Total2n + 2

The test if (n) is made once per call, that is, n + 1 times. In the n calls made while n is nonzero, the second line is executed: the result of the recursive call is added to an element and returned. This line counts as one step; the steps of the called function itself are counted separately, in the lines of that call. In the base case return 0 is executed once. The total is (n + 1) + n + 1 = 2n + 2.

At first glance this result makes rsum look faster than sum (2n + 3). But the step count is misleading here. The time of a step is independent of the input, but not all steps take the same time. A recursive call requires opening a new frame, copying the parameters, saving the return address, and removing the frame on return. This work is much more expensive than a comparison and an increment in a loop iteration. On a real machine rsum is usually slower than sum and uses extra memory.

What the step count really tells is something else: how the step count grows as n grows. 2n + 3 and 2n + 2 grow in direct proportion to n; both are linear and both are O(n). When n doubles, the time of both functions roughly doubles.

1.6.8rsum() and the call stack

A counter can be added to rsum as well:

float rsum(float list[], int n) {
  count++;               /* if test */
  if (n) {
    count++;             /* addition + return */
    return rsum(list, n - 1) + list[n - 1];
  }
  count++;
  return 0;
}

The trace of the call rsum(list, 3), together with the state of the call stack at every step, is given in Table 1.9. In the stack column, the rightmost call is the one running at that moment.

Table 1.9: Trace of the call rsum(list, 3) with the counter; list = {3, 1, 4}.
EventCall stack (bottom to top)count
rsum(list, 3): if test, 3 ≠ 0r(3)1
addition and return step; rsum(list, 2) is needed firstr(3)2
rsum(list, 2): if test, 2 ≠ 0r(3), r(2)3
rsum(list, 1) is needed firstr(3), r(2)4
rsum(list, 1): if test, 1 ≠ 0r(3), r(2), r(1)5
rsum(list, 0) is needed firstr(3), r(2), r(1)6
rsum(list, 0): if test, n = 0: base caser(3), r(2), r(1), r(0)7
return 0; the stack is at its deepestr(3), r(2), r(1), r(0)8
0 + list[0] = 3; rsum(list, 1) returns 3r(3), r(2), r(1)8
3 + list[1] = 4; rsum(list, 2) returns 4r(3), r(2)8
4 + list[2] = 8; rsum(list, 3) returns 8r(3)8

Two phases are clearly visible in the trace. In the descent phase each call makes the if test, increments count once more, and immediately opens a new call. The addition cannot be done yet, because the result of the recursive call, which is the first term of the sum, is not yet known. The stack grows to four frames. In the return phase, starting from the base case, each call adds its own element to the value it receives and returns to the call below. The additions are done in this phase, starting from list[0]. The counter does not increase in the return phase, because the addition and return steps were counted in the descent phase. The final value is count = 8 = 2 · 3 + 2.

031124listrsum(list, 3)rsum(list, 2)rsum(list, 1)rsum(list, 0)→ 0stack (bottom to top)
Figure 1.7: The deepest moment of the trace of rsum(list, 3). There are four frames on the stack; the topmost, rsum(list, 0), has reached the base case and is about to return 0.

1.6.9Matrix addition

The step count of nested loops is found the same way. The table for the function add, which adds two matrices, is in Table 1.10. The function performs c[i][j] = a[i][j] + b[i][j] for every cell.

Table 1.10: Step-count table of the matrix addition function add (s/e = 1 for every statement).
StatementFrequency
void add(int a[][MAX_SIZE], int b[][MAX_SIZE],
         int c[][MAX_SIZE], int rows, int cols) {
0
int i, j;0
for (i = 0; i < rows; i++)rows + 1
  for (j = 0; j < cols; j++)rows · (cols + 1)
    c[i][j] = a[i][j] + b[i][j];rows · cols
Total2·rows·cols + 2·rows + 1

The test of the outer loop, as in sum, is made rows + 1 times. The inner loop starts afresh on every iteration of the outer loop; each time it starts, its test is made cols + 1 times. Since the outer loop runs rows iterations, the total frequency of the inner loop test is rows · (cols + 1). The assignment is executed once for every cell, rows · cols times in total. Adding everything up:

(rows + 1) + rows · (cols + 1) + rows · cols = 2·rows·cols + 2·rows + 1

For example, for rows = 2 and cols = 4 one gets 16 + 4 + 1 = 21 steps. The formula was tested by adding a counter to the function, for four different row counts and two different column counts; in all of them the counter gave the same value as the formula.

The growth rate of the result is O(rows · cols); for a square matrix (rows = cols = n) this is O(n2). The term 2·rows in the formula depends on which dimension the outer loop runs over. If the number of rows is much larger than the number of columns (rows ≫ cols), the loops can be interchanged: the outer loop runs over columns and the inner loop over rows. The count then becomes 2·rows·cols + 2·cols + 1, and the small term shrinks. The dominant term does not change. Matrix multiplication, in contrast, requires three nested loops and is O(n3).

Common mistake

Writing the complexity of matrix addition as "O(rows, cols)". A function goes inside the O notation; separating two dimensions with a comma carries no meaning. Because the number of operations grows with the product of the two dimensions, the correct form is O(rows · cols).

1.6.10Best, average, and worst case

In the functions examined so far, the step count depended only on the size of the input: sum takes 2n + 3 steps on every array of n elements. But in many algorithms two inputs of the same size require different numbers of steps. Linear search is the simplest example: a value is compared one by one with the elements of the array from the beginning to the end, and the search stops when it is found.

071329354158▲ best: 1 comp.worst: n comp. ▲
Figure 1.8: Linear search in an array of six elements. If the sought value is in the first cell (7), a single comparison suffices; if it is in the last cell (8) or is not in the array, n comparisons are needed.

In the array {7, 3, 9, 5, 1, 8} of Figure 1.8, if 7 is searched for, it is found at the first comparison. If 8 is searched for, six comparisons are needed. If 6 is searched for, it is established after six comparisons that it is not there. These three cases are given names:

Table 1.11: Best, average, and worst case of linear search in an array of n elements.
CaseWhen?Comparisons
BestThe sought value is in the first cell1 → Θ(1)
AverageThe sought value is in the array and is equally likely to be at any position(n + 1) / 2 → Θ(n)
WorstThe sought value is in the last cell or not in the array at alln → Θ(n)
  • The best case is the cost of the input that requires the fewest steps among inputs of the same size.
  • The worst case is the cost of the input that requires the most steps.
  • The average case is the expected cost under a given probability distribution of the inputs.

The average is found as follows. Let the sought value be in the array, and let the probability of finding it at each of the n positions be 1/n. If the value is at position k (counting from 1), k comparisons are made. The expected number of comparisons is:

(1/n) · (1 + 2 + … + n) = (1/n) · n(n + 1)/2 = (n + 1)/2

For an array of six elements this is 3.5: on average half of the array is scanned. Even though it is half, the scan is directly proportional to n; so the average case is also Θ(n). The notation Θ(n) says that the step count grows at the same rate as n, that is, it stays between two constant multiples of n.

The analysis usually gives the worst case. There are two reasons. First, the worst case is a guarantee valid for every input: the algorithm never takes more steps than this on any input. In a real-time system, or in an operation a user is waiting for, this guarantee is worth more than the average. Second, computing the average case requires knowing the probability distribution of the inputs. This distribution is often unknown, and an assumed distribution may not match reality. The best case, for its part, rarely gives useful information: almost every algorithm is fast on some lucky inputs.

1.7Asymptotic notation

Finding the step count exactly is not always easy, and often it is not necessary. It is nice to know that sum takes 2n + 3 steps, but whether the number is 2n + 3 or 3n + 2 hardly matters. The real time of a step is unknown anyway; constant factors in the step count get lost in that uncertainty. What matters is how the step count grows as n grows: linearly, quadratically, exponentially? The language that answers this question stripped of constants and small terms is called asymptotic notation.

1.7.1Big O

Definition 1.5

If there exist positive constants c and n0 such that f(n) ≤ c · g(n) for all n ≥ n0, one writes f(n) = O(g(n)), read "f(n) is of order g(n)". This notation is called Big-O.

The definition allows two freedoms. The first is the constant c: not g(n) itself but some constant multiple of it must stay above f(n). This freedom makes constant factors irrelevant. The second is the constant n0: the inequality is required only for sufficiently large n. What happens at small n is ignored. Figure 1.9 shows this situation: before n0 the curve f(n) may lie above c · g(n), but after n0 it always stays below.

nstepsn₀c·g(n)f(n)f(n) ≤ c·g(n) for n ≥ n₀
Figure 1.9: The definition of Big-O. After n0 the curve f(n) stays below the curve c · g(n).

The step counts found for sum, rsum, and add are written in this notation as follows:

  • Tsum(n) = 2n + 3 = O(n). Since 2n + 3 ≤ 3n for n ≥ 3, one can choose c = 3, n0 = 3.
  • Trsum(n) = 2n + 2 = O(n). For n ≥ 2, 2n + 2 ≤ 3n.
  • Tadd = 2·rows·cols + 2·rows + 1 = O(rows · cols); O(n2) for a square matrix.

The "=" sign in the notation is not the usual equality. O(g(n)) is the set of all functions bounded from above by a constant multiple of g(n); the statement f(n) = O(g(n)) means "f(n) is an element of this set". So the statement is read in one direction only: one writes 2n + 3 = O(n), but not O(n) = 2n + 3. Big-O is an upper bound; it says how fast the function grows at most.

In this course time complexity is computed most of the time. Memory matters too, but in most problems time is the scarcer resource: missing memory can sometimes be added, while time that has passed does not come back.

1.7.2Example: 3n³ + 6n² + 7n

Example 1.3

Let f(n) = 3n3 + 6n2 + 7n. Let us show that f(n) = O(n3) by finding c and n0 that fit the definition. The method is to bound the nondominant terms step by step by the next higher power.

  1. The smallest term is 7n. For n ≥ 7, 7n ≤ n · n = n2. Hence f(n) ≤ 3n3 + 6n2 + n2.
  2. The squared terms combine: 6n2 + n2 = 7n2. Now f(n) ≤ 3n3 + 7n2.
  3. The same route once more: for n ≥ 7, 7n2 ≤ n · n2 = n3. Thus f(n) ≤ 3n3 + n3 = 4n3.
  4. We have found c = 4 and n0 = 7: for all n ≥ 7, f(n) ≤ 4n3. The definition is satisfied.
3n³ + 6n² + 7n ≤ 3n³ + 6n² + n² (7n ≤ n² for n ≥ 7)3n³ + 6n² + 7n ≤ 3n³ + 7n²3n³ + 6n² + 7n ≤ 3n³ + n³ (7n² ≤ n³ for n ≥ 7)3n³ + 6n² + 7n ≤ 4n³ ⇒ f(n) = O(n³) (c = 4, n₀ = 7)
Figure 1.10: The chain of inequalities 3n3 + 6n2 + 7n ≤ 4n3. In each line a nondominant term is raised to the next higher power under the condition n ≥ 7.

The c and n0 found are not the only choice. For example, for n ≥ 1 every term can be bounded by a multiple of n3: f(n) ≤ 3n3 + 6n3 + 7n3 = 16n3. This gives c = 16, n0 = 1. The definition requires only that some constants exist; which ones are chosen does not matter. For c = 4, n0 = 7 is indeed the smallest value: when tried with a script, at n = 6 one gets f(6) = 906 > 4 · 216 = 864.

The result has two practical readings.

  • Upper bound. If the running time is given by f(n) steps, then for n ≥ 7 the program never exceeds 4n3 steps.
  • Cubic growth. When n triples, the time grows by at most 33 = 27 times. If this algorithm sorts 100 numbers in 2 seconds, sorting 300 numbers takes at most 2 · 27 = 54 seconds; not 6 seconds.

The method in the example can be generalized.

Theorem 1.1 (Degree of a polynomial)

If f(n) = amnm + am−1nm−1 + … + a1n + a0 is a polynomial, then f(n) = O(nm).

Let n ≥ 1. For every i ≤ m, ni ≤ nm. Let us bound with the absolute values of the coefficients: f(n) ≤ |am|nm + … + |a1|n + |a0| ≤ (|am| + … + |a1| + |a0|) · nm. If c = |am| + … + |a0| and n0 = 1 are chosen, the definition is satisfied. □

The theorem says that the growth rate of a polynomial is determined by its highest-degree term. This is why 2n + 3, 100n, and n + 106 are in the same class: all are O(n).

1.7.3Ω and Θ

Big-O gives only an upper bound, and this bound can be loose. The statement 3n + 2 = O(n2) is true: for n ≥ 2, 3n + 2 ≤ 4n ≤ 4n2. Even 3n + 2 = O(2n) is true. But these statements tell little about the function. To state the growth rate of a function exactly, the notions of lower bound and tight bound are also needed.

Definition 1.6

If there exist positive c and n0 such that f(n) ≥ c · g(n) for all n ≥ n0, one writes f(n) = Ω(g(n)) (Big Omega). If there exist positive c1, c2, and n0 such that c1 · g(n) ≤ f(n) ≤ c2 · g(n) for all n ≥ n0, one writes f(n) = Θ(g(n)) (Big Theta).

Table 1.12: The three asymptotic notations (inequalities for all n ≥ n0).
NotationDefinitionMeaning
f(n) = O(g(n))f(n) ≤ c · g(n)g is an upper bound of f
f(n) = Ω(g(n))f(n) ≥ c · g(n)g is a lower bound of f
f(n) = Θ(g(n))c1 · g(n) ≤ f(n) ≤ c2 · g(n)both O and Ω: tight bound

Θ is the intersection of O and Ω: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). Θ says that the function grows at the same rate as g(n).

Example 1.4

Let us show that 3n + 2 = Θ(n). For the lower bound: for every n ≥ 1, 3n + 2 ≥ 3n; that is, c1 = 3. For the upper bound: if n ≥ 2 then 2 ≤ n and 3n + 2 ≤ 3n + n = 4n; that is, c2 = 4. Taking n0 = 2, 3n ≤ 3n + 2 ≤ 4n holds for all n ≥ 2. At n = 1 the upper bound fails (5 > 4); this is why n0 is chosen as 2.

When using asymptotic notation, the smallest possible upper bound is written. 3n + 2 = O(n2) is true but misleading; a reader may think the algorithm is quadratic. If a tight bound is known, it is written with Θ. Selection sort makes n(n − 1)/2 comparisons whatever the input. Since n2/4 ≤ n(n − 1)/2 ≤ n2/2 for n ≥ 2, selection sort is Θ(n2). In linear search, the worst case is Θ(n) and the best case is Θ(1); if a single bound valid for every input is wanted, one writes O(n).

These notations also make it easier to think when a problem can be solved better than the required bound. Suppose an exam question asks "solve it in O(n + m) time". A student has solved the problem in O(n), then, to follow the wording of the question, added an empty loop running m times at the end of the code. This is unnecessary. A solution that takes O(n) time is already O(n + m), because Big-O is an upper bound. If something better than the required bound can be done, so much the better.

1.7.4Common complexities

The time complexities of algorithms mostly fall into one of a few familiar classes. Table 1.13 gives these classes, their names, and the values they take for small n. In the table lg n means log2 n.

Table 1.13: Magnitude of the common complexity functions at small values of n.
ComplexityNamen=1n=2n=4n=8n=16n=32
1constant111111
lg nlogarithmic012345
nlinear12481632
n lg nlinearithmic0282464160
n2quadratic1416642561,024
n3cubic18645124,09632,768
2nexponential241625665,5364.29·109
n!factorial122440,3202.09·10132.63·1035

Each class has a typical source. A constant-time operation, such as accessing an element of an array by index, does not look at the size of the input. Logarithmic time is seen in algorithms that halve the problem at each step; binary search in a sorted array is an example. Linear time is the time of algorithms that look at the input once, for example sum and linear search. Linearithmic time appears in good sorting algorithms. Quadratic time comes from two nested loops and cubic time from three nested loops; selection sort and matrix multiplication are examples. Exponential and factorial times are the times of algorithms that try all subsets or all orderings.

The small values of n in the table can be misleading. At n = 4, 2n = n2 = 16; the two functions look the same. At n = 8 the exponential function has pulled ahead: 2n = 256, n2 = 64. At n = 32 the difference is expressed in billions. Beyond a certain point exponential and factorial terms crush all the polynomial terms.

1.7.5Growth graph

A graph of the same functions between n = 1 and n = 12 shows the difference even more clearly. In the upper graph of Figure 1.11 the vertical scale runs from 0 to 150. On this scale lg n, n, and n lg n separate from one another; n2 climbs quickly and reaches 144 at n = 12. n3 and 2n have long since left the graph.

050100150123456789101112n →lg nnn·lg nn²n³2ⁿ
01000200030004000123456789101112n →n·lg nn²n³2ⁿn!
Figure 1.11: Growth of the complexity functions for n = 1 … 12. In the top graph the vertical scale is 0–150, in the bottom 0–4500. In the bottom graph n! leaves the graph at n = 7; the linear functions look glued to the floor.

In the lower graph the scale is widened to 0 to 4500. At n = 12, n3 = 1728 and 2n = 4096. 2n passes n3 around n = 10 and stays ahead from then on. n! leaves the graph at n = 7 with the value 5040; at n = 6 it is only 720. On this scale n and n lg n cannot be told apart from the horizontal axis.

1.7.6A billion instructions per second

To see the effect of complexity on real time, let us imagine a machine that executes 109 instructions per second, that is, performs each step in 1 nanosecond. Table 1.14 shows how long an algorithm that takes f(n) steps would take on this machine. In the computation 1 year is taken as 365 days and 1 month as 30 days. All the values in the table were recomputed and verified with a script.

Table 1.14: Time for f(n) steps on a machine executing 109 instructions per second.
nnlg nn lg nn²n³n⁴n¹⁰2ⁿ
100.01 μs0.00332 μs0.0332 μs0.1 μs1 μs10.0 μs10.0 s1.02 μs
200.02 μs0.00432 μs0.0864 μs0.4 μs8 μs160 μs2.84 hours1.05 ms
300.03 μs0.00491 μs0.147 μs0.9 μs27.0 μs810 μs6.83 days1.07 s
400.04 μs0.00532 μs0.213 μs1.6 μs64.0 μs2.56 ms4.05 months18.3 min
500.05 μs0.00564 μs0.282 μs2.5 μs125 μs6.25 ms3.1 years13.0 days
1000.1 μs0.00664 μs0.664 μs10.0 μs1 ms100 ms31.7 centuries4.02·1011 centuries
10001 μs0.00997 μs9.97 μs1 ms1 s16.7 min3.17·1011 centuries3.40·10282 centuries
1000010.0 μs0.0133 μs133 μs100 ms16.7 min3.86 months3.17·1021 centuries6.33·102991 centuries

To see how a cell is computed, take n = 40 and f(n) = 2n. 240 ≈ 1.1 · 1012 steps is 1.1 · 1012 ns, that is, about 1100 seconds. That makes 18.3 minutes. When n grows by 10 to 50, the step count grows by a factor of 210 = 1024 and the time reaches 13 days. In exponential algorithms, adding a few elements to the input multiplies the time.

Three conclusions follow from the table. First, logarithmic and linear algorithms finish within microseconds even on ten thousand elements. Second, there are large differences among polynomial algorithms too: on ten thousand elements n2 takes 100 milliseconds, n3 takes 16.7 minutes, and n4 takes 3.86 months. Third, exponential algorithms are usable in practice only on very small inputs. For n = 100, 2n steps take 4 · 1011 centuries; the age of the universe is about 1.4 · 108 centuries. For n = 10,000 the time is about 102992 centuries.

1.7.7Amortized analysis

Worst-case analysis treats each operation on its own. But in some data structures operations are sometimes expensive and mostly cheap. In such a structure, adding up the worst-case cost of every operation makes the total cost look far larger than it is. Amortized analysis computes the total cost of a sequence of n operations and divides it by n. The result is the average cost per operation. This average does not rest on a probabilistic assumption; it is a guarantee valid for every sequence of operations.

The typical example is the dynamic array. A dynamic array starts with a certain capacity and appends elements at the end. When the array becomes full, its capacity is doubled with realloc. realloc enlarges an allocated block; if it cannot enlarge it in place, it allocates a new block and copies the old elements there. The cost of an insertion is one write plus, if any, the number of elements copied.

Example 1.5

Let 9 elements be appended to an empty array of capacity 1, with the capacity doubling each time it fills. At the 2nd insertion the array is full: 1 element is copied and the capacity becomes 2. At the 3rd insertion 2 elements are copied and the capacity becomes 4. At the 5th insertion 4 elements are copied and the capacity becomes 8. At the 9th insertion 8 elements are copied and the capacity becomes 16. The total number of copies is 1 + 2 + 4 + 8 = 15, and the total number of writes is 9. The total cost of 9 insertions is 24; this comes to 24 / 9 ≈ 2.7 operations per insertion. Looked at individually, the 9th insertion cost 9 operations, but the average stays below 3.

In the general case, the number of elements copied in n insertions is 1 + 2 + 4 + … + 2k, where 2k < n. This geometric sum is 2k+1 − 1 < 2n. Together with the writes, the total cost is less than 3n. A single insertion may take O(n), but the amortized cost per insertion is O(1). This bound was also checked with a script for different values of n between 1 and 1000; the total cost stayed below 3n every time.

Had the capacity been increased by a fixed amount, say 10, each time instead of being doubled, the result would be very different. In that case the whole array is copied once every 10 insertions, and the number of copies is 10 + 20 + 30 + … ≈ n2/20. The amortized cost per insertion rises to O(n). Growing by doubling is the idea that dynamic arrays and many library structures rest on.

1.8The magic square

A problem that shows the practical importance of asymptotic notation strikingly is the magic square. When two methods for the same problem are compared, one working by brute force and the other by a clever rule, one sees that the right algorithm makes a difference that no hardware speedup can make up for.

1.8.1The problem

Definition 1.7

A magic square of size n × n is a table in which the numbers from 1 to n2 are placed so that the sums of every row, every column, and the two main diagonals are equal.

This common sum can be computed in terms of n. The sum of the numbers from 1 to n2 is n2(n2 + 1)/2. These numbers are spread over n rows, and every row has the same sum. So the sum of one row is:

n2(n2 + 1)/2 ÷ n = n(n2 + 1)/2

For n = 3 the sum is 3 · 10 / 2 = 15, for n = 5 it is 5 · 26 / 2 = 65, and for n = 7 it is 7 · 50 / 2 = 175. Figure 1.12 shows a magic square of size 5 × 5.

15812417161475232220136432119121092251811
Figure 1.12: A 5 × 5 magic square. The sum of every row, column, and main diagonal is 65. The square was generated with Coxeter's rule: the 1 is in the middle of the first row.

Let us check the square in the figure. The first row is 15 + 8 + 1 + 24 + 17 = 65, the first column 15 + 16 + 22 + 3 + 9 = 65, the main diagonal 15 + 14 + 13 + 12 + 11 = 65, the other diagonal 17 + 5 + 13 + 21 + 9 = 65. The remaining rows and columns also add up to 65.

1.8.2Brute force versus a faster machine

The first way that comes to mind for solving the problem is brute force: trying all possible solutions one by one. The numbers from 1 to n2 can be arranged in n2 cells in (n2)! different ways. For each arrangement the row, column, and diagonal sums are checked. For a 5 × 5 square there are 25! ≈ 1.55 · 1025 arrangements. A machine that tries 109 arrangements per second tries all of them in 1.55 · 1016 seconds. Since a century is about 3.15 · 109 seconds, this time is about 4.9 million centuries.

A common objection to this computation is that a computer ten times faster, say a new 10 GHz one, would solve this problem at once, so there is no need to bother with the algorithm. The computation refutes this objection:

25! / (1010 · 3.15 · 109) ≈ 4.9 · 105 centuries

A machine ten times faster brings 4.9 million centuries down to about 490 thousand centuries. The result is still hopeless. Even a machine a thousand times faster brings the time down only to 4900 centuries. And in an algorithm of complexity (n2)!, raising n from 5 to 6 multiplies the step count by 36!/25! ≈ 2.4 · 1016; no hardware progress can cover that.

The right algorithm, on the other hand, builds the same square in only 25 steps, in far less than a microsecond. The algorithm comes before the hardware: running a slow algorithm on a fast machine is almost always worse than running a fast algorithm on a slow machine.

1.8.3Coxeter's rule and the C code

When n is odd, there is a simple rule that builds the magic square directly. Horowitz and Sahni attribute this rule to Coxeter; it is also known as the Siamese method or the de la Loubère method. The rule is this:

  1. Write 1 in the middle of the first row.
  2. For the next number always move to the upper-left diagonal: one row up, one column left.
  3. If you run off the table, wrap around from the opposite edge. A move that goes off the top goes to the bottom row, and a move that goes off the left goes to the rightmost column. The table is thought of as a torus whose opposite edges are glued together.
  4. If the upper-left diagonal cell is occupied, do not go there; instead step down to the cell directly below the current one.

The rule places each number in a single step and finishes in n2 steps: the time complexity is O(n2). Since the table itself already contains n2 cells, there cannot be a faster algorithm; every cell must be written at least once. The rule is therefore an algorithm with Θ(n2) time that cannot be bettered. The rule written in C is this:

void magic(int n, int sq[][MAX]) {
  int i = 0, j = (n - 1) / 2, s, r, c;
  sq[i][j] = 1;       /* sq must be zeroed */
  for (s = 2; s <= n * n; s++) {
    r = (i - 1 < 0) ? n - 1 : i - 1; /* up */
    c = (j - 1 < 0) ? n - 1 : j - 1; /* left */
    if (sq[r][c]) i = (i + 1) % n; /* down */
    else { i = r; j = c; }
    sq[i][j] = s;
  }
}

The code works as follows, line by line:

  • sq[][MAX] is a two-dimensional integer array whose row length is MAX. In C the second dimension of a two-dimensional array parameter must be written, because the compiler computes the address sq[i][j] as i · MAX + j. MAX is a constant defined in the program with #define and cannot be smaller than n.
  • i = 0, j = (n - 1) / 2 is the middle of the first row. For n = 5, j = 2. 1 is written there. The code assumes that all cells are zero; the caller must initialize the array to zero. Whether a cell is occupied is determined by checking whether it is nonzero.
  • The loop places every number from s = 2 to n2.
  • r and c are the row and column of the upper-left diagonal. If i - 1 < 0, the row has gone off the top; r goes to the bottom row, n - 1. The same check is made for the column. The conditional operator ? : writes this wraparound on one line.
  • If sq[r][c] is nonzero, the diagonal cell is occupied. In that case one steps down from the current cell: i = (i + 1) % n. The modulo operation wraps an overflow at the bottom edge to the top row. j does not change.
  • If the diagonal cell is empty, one moves there: i = r; j = c;. Then the number is written with sq[i][j] = s.

The code was compiled and run for n = 3, 5, and 7, and the sums of every row, column, and the two diagonals were checked with a piece of program. In all three squares the sums came out 15, 65, and 175 respectively. The output for the 5 × 5 square is the same as Figure 1.12.

1.8.4Code trace: n = 3

Let us trace the call magic(3, sq). Since the square is 3 × 3, the row and column indices take the values 0, 1, and 2. Table 1.15 gives where each number is placed and why.

Table 1.15: Trace of the call magic(3, sq). (r, c) is the upper-left diagonal.
sPrevious (i, j)(r, c)DiagonalNew (i, j)
1——middle of the first row(0, 1)
2(0, 1)(2, 0)empty; row overflowed → bottom row(2, 0)
3(2, 0)(1, 2)empty; column overflowed → rightmost column(1, 2)
4(1, 2)(0, 1)occupied (1 is there) → one down(2, 2)
5(2, 2)(1, 1)empty(1, 1)
6(1, 1)(0, 0)empty(0, 0)
7(0, 0)(2, 2)occupied (4 is there) → one down(1, 0)
8(1, 0)(0, 2)empty; column overflowed → rightmost column(0, 2)
9(0, 2)(2, 1)empty; row overflowed → bottom row(2, 1)

Two lines of the trace need care. At s = 4 the upper-left diagonal cell is (0, 1), and the 1 is there; so one steps down below the 3, to (2, 2). At s = 7 the current cell is (0, 0). The upper-left diagonal overflows both the row and the column and becomes (2, 2); the 4 is there. So one steps down below (0, 0), to (1, 0). When s = 10 > 9 the loop ends.

1324 6175324 618753294
Figure 1.13: Three moments from the trace of magic(3, sq). (a) s = 4: because the diagonal cell is occupied, 4 was written below 3. (b) s = 7: 7 was written below 6. (c) The finished square.

The resulting square is this: the first row is 6, 1, 8; the second row 7, 5, 3; the third row 2, 9, 4. The sum of every row, every column, and the two diagonals is 15 = 3 · (9 + 1)/2. For example the main diagonal is 6 + 5 + 4 = 15 and the other diagonal is 8 + 5 + 2 = 15.

1.9Measuring performance

Performance analysis states the growth rate of an algorithm independently of the machine. But it does not say how many milliseconds it will take on a real machine with a real input. The way to find out is to run the program and measure its time. A measurement also includes the constants, cache effects, and compiler optimizations that the analysis ignores. Therefore, when two algorithms are in the same complexity class, only measurement tells which one is faster.

1.9.1clock() and time()

The standard C library offers two functions for measuring time, in the header <time.h>. Table 1.16 compares how the two are used.

Table 1.16: Two ways of measuring time in C.
1. Processor time: clock()2. Calendar time: time()
Startstart = clock();start = time(NULL);
Stopstop = clock();stop = time(NULL);
Typeclock_ttime_t
Result (seconds)(double)(stop - start) / CLOCKS_PER_SECdifftime(stop, start)

clock() returns the processor time spent since the start of the program, in clock ticks. The number of ticks per second is given by the constant CLOCKS_PER_SEC. The difference between two measurements is converted to seconds by dividing by this constant. The (double) cast must be applied before the division; otherwise the quotient of two integers drops the fraction and 0.4 seconds comes out as 0. The resolution of clock() is limited by the tick interval of the system: a job that finishes between two ticks seems to take 0 time.

time(), on the other hand, gives the wall clock, that is, calendar time, in seconds. difftime returns the difference between two times as a double. Its resolution is one second; it is suitable for jobs that last minutes and too coarse for short ones. time() also includes the time of other programs running on the computer at that moment.

The name CLK_TCK turns up in old books and old code. This name is nonstandard and a leftover from old compilers; most of today's compilers do not recognize it. In standard C, CLOCKS_PER_SEC is used.

There is one more rule when measuring: operations with peripherals, that is, writing to the screen, writing to disk, or sending to a printer, are very slow compared with the speed of the processor. If a printf is left inside the measured region, the measured time is largely the time of the printf; the time of the algorithm is overshadowed by it. printfs must be kept outside the measured region.

1.9.2Timing selection sort

The program that measures the real time of selection sort on arrays of different sizes is this:

#include <stdio.h>
#include <time.h>
#define MAX_SIZE 5001
#define ITERATIONS 20
void sort(int list[], int n);   /* selection sort */

int main(void) {
  int i, j, list[MAX_SIZE];
  int sizelist[] = { 0, 100, 300, 600, 900, 1200, 1500, 2000,
    3000, 3100, 3200, 3300, 3400, 3500, 3600, 3700, 3800,
    3900, 4000, 5000 };
  clock_t start, stop;  double ms;
  for (i = 0; i < ITERATIONS; i++) {
    for (j = 0; j < sizelist[i]; j++)
      list[j] = sizelist[i] - j;   /* descending array */
    start = clock();
    sort(list, sizelist[i]);
    stop = clock();
    ms = 1000.0 * (stop - start) / CLOCKS_PER_SEC;
    printf("%4d elements: %6.1f ms\n", sizelist[i], ms);
  }
  return 0;
}
  • The array sizelist holds the 20 sizes to be measured: from 0 to 5000. The sizes are chosen densely between 3000 and 4000, so that the times of neighboring sizes can be compared.
  • For each size the array is filled from largest to smallest with list[j] = sizelist[i] - j. Because the number of comparisons of selection sort is independent of the input, a descending array is not a special case; but it ensures that every measurement is made with the same kind of input.
  • Between the two clock() calls there is only the call to sort. Filling the array and printing the result are outside the measured region.
  • ms = 1000.0 * (stop - start) / CLOCKS_PER_SEC converts the time to milliseconds. 1000.0 is a double constant; so the whole expression is computed with double arithmetic. In old code this line appears in the form (int)(1000*(stop-start)/CLK_TCK); integer division drops the fraction and CLK_TCK is nonstandard. That is why double arithmetic with 1000.0 is more correct.
  • The definition of sort is not given in the program; the selection sort function and the SWAP macro must be added to the same file. MAX_SIZE is 5001; the largest measured size, 5000 elements, fits.

1.9.3Results and discrepancies

A sample output of the program on an old machine is plotted in Figure 1.14. The dots show the measured times, and the dashed curve shows a curve c · n2. The general trend agrees with the analysis: time grows with n2. But there are oddities in the details.

050100150200250010002000300040005000n (number of elements)ms
Figure 1.14: Single-run measurement results of selection sort. The dots are sample measurements, and the dashed curve shows the trend c · n2. The red dots are measurements that look inconsistent.
  • Up to 600 elements, all measurements came out as 0 ms. The sorting did take time, but it took too little to be measured.
  • 3000 elements took 110 ms, while 3100 elements took 93 ms. A larger input seems to have taken less time.
  • 3500, 3600, and 3700 elements all took 125 ms; there is no difference among them.

The cause of these oddities is the resolution of clock(). The counter increases only at a clock tick. If the sorting starts and ends between two ticks, stop - start = 0. On a system with a tick interval of about 15.6 ms, all results are rounded to multiples of 15–16 ms: 93, 110, and 125 ms correspond to six, seven, and eight ticks respectively. The real time can deviate by as much as a tick. So the "reversed" difference between 3000 and 3100 elements is not real. In addition, the operating system can pause the program for a short time during the measurement and run another job; this also spoils single measurements.

The program was also run on a present-day machine, the one on which these notes were prepared. The results for selected sizes are given in Table 1.17. The code was compiled without optimization (-O0); on this machine the resolution of clock() is 1 ms. Times vary with the machine, the compiler, and the build options.

Table 1.17: Single-run measurement of selection sort on a present-day machine (ms; varies by machine).
n3006001200200030003500360040005000
ms014112340373864

The machine is many times faster than the old one, but the oddity persists: 3500 elements took 40 ms and 3600 elements took 37 ms. A resolution of 1 ms is still coarse for short measurements; single measurements are also open to interference from the operating system. The solution to this problem is to repeat every measurement many times and take the average.

Common mistake

Measuring a short job with a single clock() measurement. The result either comes out 0 or is rounded to multiples of a tick interval. A job that takes microseconds, such as a search, must be repeated thousands of times inside the measured region, and the total time divided by the number of repetitions.

1.9.4Linear search with a sentinel

Let us see repeated measurement on linear search. The search function uses a small trick:

int seqsearch(int list[], int searchnum, int n) {
  int i;
  list[n] = searchnum;          /* sentinel */
  for (i = 0; list[i] != searchnum; i++)
    ;
  return (i < n) ? i : -1;
}

In the loop of an ordinary linear search, two tests are made in every iteration: i < n (has the end of the array been reached?) and list[i] != searchnum (has the sought value been found?). seqsearch removes the first test. It writes the sought value just past the end of the array, into list[n]. This cell is called a sentinel. Even if the sought value is not in the array, the loop stops at the sentinel at the latest; so no bounds check is needed. When the loop stops, if i < n then the value has really been found in the array and its index is returned. If i == n, the loop has stopped at the sentinel, and -1 is returned to report that the value was not found.

The sentinel trick has a price: for n elements, n + 1 places must be reserved in the array. This is why MAX_SIZE = 5001 was chosen in the measurement program. The sentinel also modifies the array; the old value in list[n] is lost. That is why the measurement program erases the sentinel after each size.

In the worst case, that is, when the sought value is not in the array, seqsearch makes n + 1 comparisons: n elements and the sentinel. The time is O(n); the best case, when the sought value is in the first cell, is Θ(1). The sentinel does not change the number of comparisons, but it cuts the number of tests per iteration from two to one; the loop can become roughly twice as fast.

1.9.5Code trace: seqsearch()

Let us trace the call seqsearch(list, 5, 3) on the array list = {4, 8, 2}. The array has three elements, but space is also reserved for list[3]. The value 5 is being sought.

  1. list[3] = 5: the sentinel is put in place. The loop will now stop here at the latest (Figure 1.15a).
  2. i = 0: list[0] = 4 ≠ 5, i becomes 1. Only one test is made; there is no bounds check.
  3. i = 1: list[1] = 8 ≠ 5, i becomes 2.
  4. i = 2: list[2] = 2 ≠ 5, i becomes 3.
  5. i = 3: list[3] = 5; the loop stops. But the value found is the sentinel (Figure 1.15b).
  6. i = 3 < n is false; the function returns -1: 5 is not in the array. In total n + 1 = 4 comparisons have been made.
04182235sentinel
04182235▲ isentinel
Figure 1.15: seqsearch({4, 8, 2}, 5, 3). (a) The sentinel was written to list[3]. (b) The loop stopped at i = 3, on the sentinel; the result is -1.

If 8 is searched for in the same array, the loop stops at i = 1; since 1 < 3, the function returns 1. These two calls were compiled and run, and the results were verified as -1 and 1.

1.9.6Repeated measurement

A search alone takes microseconds; its time cannot be found with a single measurement. The measurement program therefore repeats the search many times for each size. The measurement part of the program is this:

start = clock();
for (j = 0; j < runtimes[i]; j++)
  pos = seqsearch(list, -1, sizelist[i]);
stop = clock();
total = 1000.0 * (stop - start) / CLOCKS_PER_SEC;
avg = 1000.0 * total / runtimes[i];  /* microsec */
list[sizelist[i]] = sizelist[i];  /* erase sentinel */
  • For every n the search is repeated runtimes[i] times. The repetition count is large for small sizes (500,000) and small for large sizes (5000). That way the total measurement time of each size is much longer than a few ticks, yet the measurement does not take minutes.
  • -1 is searched for. Since the array contains only numbers from 0 to n − 1, -1 is never found; every search is in the worst case and makes exactly n + 1 comparisons.
  • total is the total time in milliseconds. avg = 1000.0 * total / runtimes[i] gives the average time of a single search in microseconds: multiplying milliseconds by 1000 converts them to microseconds.
  • The last line erases the sentinel: it writes the old value, that is n, back into list[n]. The array is assumed to have been filled with list[j] = j.
05101520010002000300040005000n (number of elements)μs / search
Figure 1.16: Average search times found by repeated measurement (μs per search). The dots are the measured averages, and the dashed line shows the linear trend.

Figure 1.16 shows the results. The averages are no longer 0 and grow linearly with n; this agrees with the expectation of O(n). The fluctuation after 3000 is caused by the decrease in the repetition count: as runtimes gets smaller, the total time also gets shorter and the measurement becomes coarse again. The machine on which the measurement was made had 1000 ticks per second; that is, one tick is 1 ms.

The same measurement was also made while preparing these notes on a present-day machine. About 0.4 μs per search was measured at 100 elements, about 3.4 μs at 1000 elements, and about 18 μs at 5000 elements. The values vary by machine, but their ratios stay the same: when n grows tenfold, the time also grows about tenfold. The way to proceed when measuring short jobs, in brief, is this: the job is repeated many times, the total time is measured, and it is divided by the number of repetitions.

1.10Recursive routines

The function rsum showed how a problem can be solved with a smaller copy of itself. The same approach makes it possible to translate directly into code many functions that are defined recursively in mathematics. Every recursive routine has two parts: a base case that gives a result without calling itself, and a recursive step that reduces the problem to a smaller one.

1.10.1Factorial, Fibonacci, and the binomial coefficient

Let us take three classic functions:

  • Factorial. n! = n · (n − 1)! and 0! = 1! = 1. The base case is n ≤ 1, and the step is n · fact(n − 1).
  • The Fibonacci sequence. f0 = 0, f1 = 1, and for i > 1, fi = fi−1 + fi−2. The base case is n ≤ 1 and the result is n itself; the step is fib(n − 1) + fib(n − 2).
  • The binomial coefficient. C(n, m) = n! / (m! · (n − m)!) is the number of ways of choosing m of n elements. The relation of Pascal's triangle is C(n, m) = C(n − 1, m) + C(n − 1, m − 1). The base case is m = 0 or m = n; in both the result is 1.

The definitions translate into C almost word for word:

long fact(long n) {
  if (n <= 1) return 1;
  return n * fact(n - 1);
}

long fib(long n) {
  if (n <= 1) return n;   /* f0 = 0, f1 = 1 */
  return fib(n - 1) + fib(n - 2);
}

long binom(int n, int m) {
  if (m == 0 || m == n) return 1;
  return binom(n - 1, m) + binom(n - 1, m - 1);
}

When compiled and run, the code gave fact(5) = 120, fact(10) = 3628800, fib(10) = 55, binom(5, 2) = 10, and binom(10, 3) = 120. Let us trace the call fact(3). fact(3) wants to compute 3 · fact(2); fact(2) wants to compute 2 · fact(1); fact(1) is the base case and returns 1. On the way back, fact(2) returns 2 · 1 = 2 and fact(3) returns 3 · 2 = 6. As in rsum, the stack first grows and then shrinks.

Common mistake

Writing fib(n - 1) * fib(n - 2) in the Fibonacci step. Since the base values are 0 and 1, the product always gives 0 or 1: f2 = 1 · 0 = 0, f3 = 0 · 1 = 0, and 0 from then on. By definition the step is an addition. A common mistake with the binomial coefficient is to write the function without parameters, as long binom(); n and m must be parameters, because every recursive call is made with different values.

1.10.2Cost

fact(n) calls itself n − 1 times and does constant work in each call. Its time is O(n); the stack depth is also n. The same job can be done with a loop in O(n) time but with O(1) memory.

fib and binom, in this form, take exponential time. The reason is clear: the same subproblems are solved again and again. fib(5) calls fib(4) and fib(3); fib(4) in turn calls fib(3) again. fib(3) is computed twice and fib(2) three times. The total number of calls is 2fn+1 − 1. In an experiment with a counter, fib(10) made 177 calls, fib(20) made 21,891, and fib(30) made 2,692,537. With every increase of 10, the number of calls grows by a factor of about 123. The stack depth, in contrast, is only n, because at most n frames are on the stack at the same time. Fibonacci numbers can be computed in O(n) time with a loop that keeps the last two values. Reducing exponential time to linear or polynomial time by storing the results of repeated subproblems is one of the important ideas of algorithm design.

1.11Complexity summary

The time and extra memory requirements of the routines examined in these notes are collected in Table 1.18.

Table 1.18: Complexities of the routines examined in these notes.
RoutineTimeExtra memoryRemark
sort (selection sort)Θ(n2)O(1)n(n − 1)/2 comparisons, at most n − 1 swaps
sumΘ(n)O(1)2n + 3 steps
rsumΘ(n)O(n)2n + 2 steps, n + 1 frames
add (matrix addition)Θ(rows · cols)O(1)Θ(n2) for a square matrix
seqsearchO(n)O(1)best Θ(1), worst n + 1 comparisons
magic (Coxeter)Θ(n2)O(1)brute force: (n2)! arrangements
dynamic array insertionO(1) amortizedO(n)a single insertion is O(n) in the worst case
fib (recursive)exponentialO(n)stack depth n

The "extra memory" column in the table does not count the input itself. sort, sum, and add use only a few local variables. rsum and fib take space proportional to n on the call stack. The O(n) memory of the dynamic array is the block that holds the elements itself: the capacity is at most twice the number of elements, and during reallocation the old and new blocks briefly coexist.

1.12Common mistakes

  1. Assuming "it compiled and ran, so it is correct". A program may give the right result on one example yet work wrongly on empty input, a single element, or repeated values. The test data must cover all scenarios. The faulty version of sort likewise gives correct results but is not the intended algorithm.
  2. Confusing the step count with constants. 2n + 3 and 100n are in the same class: both are O(n). Asymptotic notation deliberately drops constant factors and small terms.
  3. Taking a loose upper bound for the best bound. 3n + 2 = O(n2) is true but tells nothing. The smallest possible g(n) is written; if a tight bound is known, Θ is used.
  4. Measuring a short job with a single clock() run. The result is 0 or a multiple of the tick interval. The job must be repeated many times and the average taken.
  5. Leaving a printf in the measured region. The input/output time overshadows the time of the algorithm.
  6. Giving a macro an argument with a side effect. SWAP(a[i++], a[j], t) increments i twice and destroys a value.
  7. Not checking the result of malloc and not giving back allocated memory. The first leads to null pointer access, the second to a memory leak.

1.13Summary

  • Process. Software goes through the phases of requirements, analysis, design, coding, and verification. In design, data objects are defined as ADTs and operations as algorithms. Postponing the implementation makes it possible to choose better.
  • Algorithm. A finite sequence of instructions satisfying the criteria of input, output, definiteness, finiteness, and effectiveness. Programs that do not terminate are computational procedures.
  • Abstraction. An ADT separates the specification from the implementation. In C the tools for this are the header file and the opaque type: the user holds only a Fraction *, and the fields are hidden in the .c file. The contract and the ownership rule of the interface must be written down explicitly.
  • Selection sort. In each round the smallest of the remaining part is moved to the front. It makes n(n − 1)/2 comparisons on every input and is Θ(n2); the number of swaps is at most n − 1. The swap is done by passing the addresses of the variables, with a function or with a macro.
  • Counting. Memory is S(P) = c + SP(I). Time is counted in program steps: sum takes 2n + 3, rsum 2n + 2, and add 2·rows·cols + 2·rows + 1 steps. Recursion opens a frame on every call and uses memory.
  • Classification. O is the upper, Ω the lower, and Θ the tight bound. The worst case is usually given, because it is a guarantee for every input. Amortized analysis looks at the total cost of a sequence of operations; in a dynamic array that grows by doubling, insertion is amortized O(1).
  • Growth. Small n misleads. 2n and n! become hopeless in no time. In the magic square, brute force takes millions of centuries and Coxeter's rule takes microseconds: the algorithm comes before the hardware.
  • Measurement. Time is measured with clock(); short jobs are repeated and averaged; input/output is kept outside the measured region. A sentinel removes the bounds test in every iteration of linear search.

1.14Key terms

  • system life cycle
  • bottom-up
  • top-down
  • algorithm
  • abstract data type (ADT)
  • implementation
  • header file
  • incomplete type
  • opaque type
  • struct
  • typedef
  • arrow operator (->)
  • malloc
  • free
  • null pointer (NULL)
  • memory leak
  • dangling pointer
  • sorting
  • selection sort
  • swap
  • macro
  • preprocessor
  • dereference (*)
  • performance analysis
  • space complexity
  • time complexity
  • program step
  • recursion
  • base case
  • call stack
  • stack frame
  • stack overflow
  • best / average / worst case
  • asymptotic notation
  • Big O
  • Big Omega
  • Big Theta
  • exponential
  • amortized analysis
  • dynamic array
  • capacity
  • realloc
  • magic square
  • brute force
  • linear (sequential) search
  • sentinel

1.15Test Yourself

  1. In the fragment for (i = 0; i < n; i++) for (j = i; j < n; j++) x++;, how many times is x++ executed? What is the value for n = 4, and which class is the time of the fragment in?

    Answer

    In round i the inner loop runs n − i times. The total is n + (n − 1) + … + 1 = n(n + 1)/2. For n = 4, 4 · 5 / 2 = 10. The fragment is Θ(n2).

  2. In the claim 5n2 + 20n + 50 = O(n2), if c = 6 is chosen, what is the smallest n0?

    Answer

    The inequality 5n2 + 20n + 50 ≤ 6n2 is equivalent to 20n + 50 ≤ n2. At n = 22, 490 > 484; at n = 23, 510 ≤ 529, and it holds from then on. The smallest n0 is 23. If c = 75 is chosen, n0 = 1 suffices.

  3. How many program steps does the following function, which finds the largest element of an array, take in the worst and in the best case? int find_max(int a[], int n) { int m = a[0]; int i; for (i = 1; i < n; i++) if (a[i] > m) m = a[i]; return m; }

    Answer

    The assignment is 1 step, the for test n times, the if test n − 1 times, and the return 1 step. The assignment m = a[i] is executed n − 1 times in the worst case (when the array is in ascending order) and not at all in the best case (when the largest element is first). The worst case is 3n and the best case 2n + 1 steps; both are Θ(n). The version with a counter gives 18 and 13 for n = 6.

  4. How many comparisons and how many real swaps (i ≠ min) does selection sort make on the array {5, 4, 3, 2, 1}?

    Answer

    The number of comparisons is independent of the input: 5 · 4 / 2 = 10. Swaps: at i = 0 5 and 1 are exchanged, at i = 1 4 and 2; the array becomes {1, 2, 3, 4, 5}. At i = 2 and i = 3, min = i. In total 2 real swaps are made.

  5. How many comparisons does seqsearch with a sentinel make on an array of five elements when searching for a value that is not in the array? How many when the sought value is at index 2?

    Answer

    If the value is absent, n + 1 = 6 comparisons are made, with the five elements and the sentinel. If the value is at index 2, 3 comparisons are made, with list[0], list[1], and list[2]; the loop stops at i = 2 and since 2 < 5, 2 is returned.

  6. 20 elements are appended to an empty dynamic array of capacity 4, with the capacity doubling each time it fills. How many elements are copied in total? What is the total cost including the writes?

    Answer

    At the 5th insertion 4 elements are copied, at the 9th 8, and at the 17th 16: 28 in total. The total cost with the writes is 28 + 20 = 48; this comes to 2.4 operations per insertion and stays below the bound 3n = 60.

  7. How many times in total does the recursive call fib(5) call fib, including the first call? How many fib frames are on the stack at the deepest moment?

    Answer

    The number of calls is 2f6 − 1 = 2 · 8 − 1 = 15. It can also be counted by hand: from the relation T(n) = T(n − 1) + T(n − 2) + 1, T(0) = T(1) = 1, one gets T(2) = 3, T(3) = 5, T(4) = 9, T(5) = 15. Since the deepest chain is fib(5) → fib(4) → fib(3) → fib(2) → fib(1), there are at most 5 frames on the stack.

  8. A Θ(n2) algorithm takes 1 second on 1000 elements. About how long does it take on 4000 elements? How many elements can be processed in 1 second on a machine ten times faster?

    Answer

    When n quadruples, the time grows by a factor of 42 = 16: about 16 seconds. On a machine ten times faster, ten times as many steps are taken in 1 second; if n2 grows tenfold, n grows by a factor of √10 ≈ 3.16. About 3160 elements are processed. For a quadratic algorithm, making the machine ten times faster enlarges the input only threefold.

  9. In a 5 × 5 magic square built with Coxeter's rule, into which cell is the number 2 written? Why?

    Answer

    1 is written in the middle of the first row, at (0, 2). The upper-left diagonal cell is (−1, 1); since the row overflows the top, it wraps to the bottom row and becomes (4, 1). The cell is empty; 2 is written there. In Figure 1.12 the 2 can be seen in the second cell of the bottom row.

  10. What happens if Fraction f; f.num = 3; is written in main.c? Why?

    Answer

    A compile error results. main.c sees only fraction.h, and there struct fraction is an incomplete type: the compiler does not know its size or fields. Therefore a variable of this type cannot be defined and its fields cannot be accessed. The user can work with fractions only through a Fraction * pointer and the functions in the interface; that is the purpose of the opaque type.

1.16Further reading

  • E. Horowitz, S. Sahni, and S. Anderson-Freed, Fundamentals of Data Structures in C (2nd ed.), Chapter 1: the basis of these notes; it presents the system life cycle, the ADT, step-count tables, asymptotic notation, the magic square, and performance measurement with more exercises.
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (3rd ed.), Chapters 2–3 and 17: defines algorithm analysis and the notations O, Ω, and Θ precisely and with proofs, and treats amortized analysis in detail with the dynamic table example.
  • R. Sedgewick, Algorithms in C: presents the principles of algorithm analysis with C code and many measurements; shows how theoretical predictions are compared with experiments.
  • B. W. Kernighan and D. M. Ritchie, The C Programming Language (2nd ed.): the reference for pointers, structures, the preprocessor, and the standard library (<stdlib.h>, <time.h>).

1.17References

  1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2nd ed., Chapter 1.
  2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed.: Chapters 2–3 (analysis, asymptotic notation), Chapter 17 (amortized analysis).
  3. B. W. Kernighan, D. M. Ritchie, The C Programming Language, 2nd ed.
  4. R. Sedgewick, Algorithms in C.

Related pages: Chapter 1 slides · © Sercan Külcü. All rights reserved.