Notacion Orden De

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:

I. 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):

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

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

C. Traversal of a tree with n nodes;

D. Calculating iteratively n-factorial; finding iteratively the nth Fibonacci number.

III. O(n2) - quadratic time

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

Examples:

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

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

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

IV. O(log n) - logarithmic time

Examples:

A. Binary search in a sorted list of n elements;

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

C. Insert and Remove operations for a heap with n nodes.

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

Examples:

A. More advanced sorting algorithms - quicksort, mergesort

VI. O(an) (a > 1) - exponential time

Examples:

...