Unit 1e – Runtime Analysis

What is Big-O notation?

Describes worst-case growth rate of algorithm runtime.

Sequential search: O(n)

Binary search: O(log n)

Bubble sort: O(n²)

What are common g++ options?

-o prog → name output file

-g → debug info

-Wall → warnings

How do you compile multiple files?

g++ main.cpp helper.cpp -o prog

Without a prototype, a compile-error is generated

What are prototypes and header files for?

Prototypes go in .h files, which are #included in .cpp files to avoid duplication.

Rules for headers?

Don’t compile .h files directly.

Recompile .cpp files if header changes.

Algorithms:

An ordered set of unambiguous, executable steps that defines a terminating process

Runtime:

Worst case run time