Algorithm

Algorithm is a step by step procedure, which defines a set of instructions to be executed in certain order to get the desired output. In term of data structures, following are the categories of algorithms.

• Search − Algorithms to search an item in a datastrucure.

• Sort − Algorithms to sort items in certain order

• Insert − Algorithm to insert item in a datastructure

• Update − Algorithm to update an existing item in a data structure

• Delete − Algorithm to delete an existing item from a data structure

Algorithm analysis

Algorithm analysis deals with the execution time or running time of various operations of a data structure. Running time of an operation can be defined as no. of computer instructions executed per operation. As exact running time of any operation varies from one computer to another computer, we usually analyze the running time of any operation as some function of n, where n is the no. of items processed in that operation in a datastructure.

Asymptotic analysis

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation. For example, running time of one operation is computed as f(n) and of another operation as g(n²). Which means first operation running time will increase linearly with the increase in n and running time of second operation will increase exponentially when n increases. Similarly the running time of both operations will be nearly same if n is significantly small.

Asymptotic Notations

Following are commonly used asymptotic notations used in calculating running time complexity of an algorithm.

• Ο Notation

• Ω Notation

• θ Notation

Big Oh Notation, Ο

The Ο(n) is the formal way to express the upper bound of an algorithm”s running time. It measures the worst case time complexity or longest amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Big Oh notation is used to simplify functions. For example, we can replace a specific functional equation 7nlogn + n – 1 with Ο(f(nlogn)). Consider the scenario as follows −

7nlogn +n – 1 ≤ 7nlogn + n

7nlogn +n – 1 ≤ 7nlogn + nlogn

for n ≥ 2 so that logn ≥ 1

7nlogn +n – 1 ≤ 8nlogn

It demonstrates that f(n) = 7nlogn +n – 1 is within the range of outout of O(nlogn) using constants c = 8 and n₀ = 2.

Omega Notation, Ω

The Ω(n) is the formal way to express the lower bound of an algorithm”s running time. It measures the best case time complexity or best amount of time an algorithm can possibly take to complete.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Theta Notation, θ

The θ(n) is the formal way to express both the lower bound and upper bound of an algorithm”s running time. It is represented as following.

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }