Big-O Notation Analysis Of Algorithms printable pdf download

Big-O Notation Analysis Of Algorithms

Big-O Notation

Analysis of Algorithms

(how fast does an algorithm grow with respect to N)

(Note: Best recollection is that a good bit of this document comes from C++ For You++, by Litvin & Litvin)

The time efficiency of almost all of the algorithms we have discussed can be characterized by only a few growth rate functions:

O(l) - constant time

This means that the algorithm requires the same fixed number of steps regardless of the size of the task.

Examples (assuming a reasonable implementation of the task):

A. Push and Pop operations for a stack (containing n elements);

B. Insert and Remove operations for a queue.

II.

O(n) - linear time

This means that the algorithm requires a number of steps proportional to the size of the task.

Examples (assuming a reasonable implementation of the task):

Traversal of a list (a linked list or an array) with n elements;

Finding the maximum or minimum element in a list, or sequential search in an unsorted list of n elements;

Traversal of a tree with n nodes;

Calculating iteratively n-factorial; finding iteratively the n

Fibonacci number.

III.

O(n

) - quadratic time

The number of operations is proportional to the size of the task squared.

Examples:

Some more simplistic sorting algorithms, for instance a selection sort of n elements;

Comparing two two-dimensional arrays of size n by n;

Finding duplicates in an unsorted list of n elements (implemented with two nested loops).

IV.

O(log n) - logarithmic time

Examples:

Binary search in a sorted list of n elements;

Insert and Find operations for a binary search tree with n nodes;

Insert and Remove operations for a heap with n nodes.

O(n log n) - "n log n " time

Examples:

More advanced sorting algorithms - quicksort, mergesort

VI.

O(a

) (a > 1) - exponential time

Examples:

Recursive Fibonacci implementation

Towers of Hanoi

Generating all permutations of n symbols

Big-O Notation Analysis Of Algorithms