Page 28 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 2: Data Structure Operations and Algorithms Complexity

O(n) - Linear Time Notes

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

Example: (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 nth Fibonacci number.

2
O(n ) - Quadratic Time
The number of operations is proportional to the size of the task squared.

Example:
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).
O(log n) - Logarithmic Time

Example:

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

Example:

It includes more advanced sorting algorithms. For example, quicksort, mergesort
O(a ) (a > 1) – Exponential Time
n

Example:

Recursive Fibonacci implementation
Towers of Hanoi
Generating all permutations of n symbols
The best time in the above list is obviously constant time, and the worst is exponential time
which, as we have seen, quickly overwhelms even the fastest computers even for relatively
small n.

LOVELY PROFESSIONAL UNIVERSITY 21