Analysis of an Algorithm

 

Analysis of an Algorithm

Algorithm Analysis is the process of evaluating an algorithm to determine its efficiency in terms of time and memory requirements as the size of the input increases.

In Data Structures, algorithm analysis helps us to compare different algorithms and select the most efficient one for solving a particular problem.

1. Why do we analyse an algorithm?

Suppose we have two algorithms for searching an element:

• Algorithm A takes 10 seconds

• Algorithm B takes 1 second

Clearly, Algorithm B is more efficient. However, simply measuring execution time on one computer is not sufficient because execution time depends on:

• Processor speed

• Programming language

• Compiler

• Operating system

• Input data

• System load

Therefore, algorithms are generally analysed based on their growth rate with respect to input size.

---

2. Main Factors in Algorithm Analysis

There are mainly two factors:

Factor	Meaning	Example
Time Complexity	Amount of time/number of basic operations required by an algorithm	O(n)
Space Complexity	Amount of memory required by an algorithm	O(1)

Time Complexity

Time complexity describes how the running time of an algorithm grows as the input size n increases.

For example:

for(int i = 0; i < n; i++)
{
    cout << i;
}

The loop executes n times.

Therefore:

Time Complexity = O(n)

---

Space Complexity

Space complexity describes how much additional memory an algorithm requires as the input size increases.

For example:

int sum = 0;

for(int i = 0; i < n; i++)
{
    sum = sum + i;
}

Only a few variables are used irrespective of n.

Therefore:

Space Complexity = O(1)

---

3. Cases in Algorithm Analysis

An algorithm can be analysed in three cases:

Case	Meaning	Example
Best Case	Minimum time required by the algorithm	Element found at first position
Average Case	Expected/average time required	Element found somewhere in the middle
Worst Case	Maximum time required	Element found at last position or not found

For example, consider Linear Search:

Array: 10  20  30  40  50
Search: 10

If 10 is found at the first position:

Best Case = O(1)

If the required element is somewhere in the middle:

Average Case = O(n)

If the element is at the last position or absent:

Worst Case = O(n)

---

4. Asymptotic Notations

To express algorithm complexity, we commonly use:

Big-O Notation — O

Represents the upper bound, commonly used for describing worst-case growth.

Examples:

O(1)       Constant
O(log n)   Logarithmic
O(n)       Linear
O(n log n) Linearithmic
O(n²)      Quadratic
O(2ⁿ)      Exponential

Growth Order

From generally more efficient to less efficient:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

---

5. Simple Example

Consider:

void display(int A[], int n)
{
    for(int i = 0; i < n; i++)
    {
        cout << A[i] << " ";
    }
}

Here, the loop executes n times.

Therefore:

Time Complexity = O(n)

Only a constant number of extra variables are used.

Therefore:

Space Complexity = O(1)

In one line:

Analysis of an algorithm is the systematic study of its time and space requirements to determine its efficiency and scalability for different input sizes.