Analyzing Algorithms -Insertion Sort

The analysis of algorithms is one of the central topics in Algorithm Analysis. The objective is to predict the computational resources required by an algorithm, primarily:

Running time
Memory usage

Among these, running time analysis is the most fundamental.

1. Why Analyze Algorithms?

Different algorithms solving the same problem may require vastly different amounts of resources.

For example:

One sorting algorithm may complete in milliseconds.
Another may require minutes for the same input size.

Algorithm analysis helps us:

Compare algorithms objectively
Predict scalability
Estimate performance for large inputs
Select efficient solutions

2. Computational Model: RAM Model

To analyze algorithms, we need a mathematical model of computation.

The standard model used in algorithm analysis is the:

Random Access Machine (RAM) Model

Characteristics of RAM Model

1. Sequential Execution

Instructions execute one after another.

There is:

No parallel execution
No concurrency

2. Constant-Time Primitive Operations

Each primitive operation takes constant time.

Examples include:

Arithmetic Operations

Addition
Subtraction
Multiplication
Division
Modulus

Data Movement

Load
Store
Copy

Control Operations

Branching
Function call
Return

3. Word Size Assumption

When input size is $n$ , integers are assumed to fit within:

$c\log n$

bits for some constant $c \geq 1$ .

This assumption ensures:

We can index array elements
Word size does not grow arbitrarily

3. What is Running Time?

The running time of an algorithm is:

The number of primitive operations executed.

Instead of measuring:

Seconds
CPU cycles

we count:

Comparisons
Assignments
Arithmetic operations
Loop iterations

This makes the analysis:

Machine independent
Language independent

4. Input Size

Running time depends on the size of the input.

Examples

Problem	Input Size
Sorting	Number of elements $n$
Integer multiplication	Number of bits
Graph algorithms	Number of vertices and edges

5. Insertion Sort Algorithm

Insertion sort works similarly to sorting playing cards in hand.

At each step:

One element is selected
Inserted into its correct position among previously sorted elements

Pseudocode of Insertion Sort


INSERTION-SORT(A)

for j = 2 to length(A)
    key = A[j]

    i = j - 1

    while i > 0 and A[i] > key
        A[i + 1] = A[i]
        i = i - 1

    A[i + 1] = key

6. Basic Idea of Analysis

In algorithm analysis:

Each statement takes constant time
Different statements may have different constants

Suppose:

Line $i$ takes time $c_i$

Then:

\text{Running Time} = \sum (\text{Cost of Statement}) \times (\text{Number of Executions})

7. Step-by-Step Analysis of Insertion Sort

Assigning Costs and Total Running Time

Important Observation

The value of:

t_j

depends on the input.

Thus:

Running time varies with input arrangement.

8. Best-Case Analysis

Best Case Condition

The array is already sorted.

Example:

[1,2,3,4,5]

For every iteration:

The while condition fails immediately.

Therefore:

t_j = 1

for all $j$ .

Running Time in Best Case

Substituting:

t_j=1

into the running-time formula:

T(n)=c_1n+c_2(n-1)+c_4(n-1)+c_5(n-1)+c_8(n-1)

Simplifying:

T(n)=an+b

for constants $a$ and $b$ .

Best-Case Complexity

Therefore:

T(n)=\Theta(n)

Insertion sort runs in linear time in the best case.

Interpretation

When data is already sorted:

Very few comparisons occur
No shifting is needed

Thus insertion sort becomes highly efficient.

9. Worst-Case Analysis

Worst Case Condition

The array is reverse sorted.

Example:

[5,4,3,2,1]

Each new element must move all the way to the beginning.

Value of $t_j$

For each iteration:

t_j = j

because:

The while loop compares with all previous elements
One extra comparison occurs when the loop exits

Summations Required

We use the arithmetic series:

\sum_{j=1}^{n} j

whose value is:

$\sum_{j=1}^{n} j=\frac{n(n+1)}{2}$

Also:

$\sum_{j=2}^{n}(j-1)=\frac{n(n-1)}{2}$

Substituting into Running-Time Formula

After substitution and simplification:

T(n)=an^2+bn+c

where $a,b,c$ are constants.

Worst-Case Complexity

Thus:

T(n)=\Theta(n^2)

Insertion sort has quadratic worst-case running time.

Interpretation

In reverse order:

Every element shifts repeatedly
Large number of comparisons occur

Hence execution time grows quadratically.

10. Average-Case Analysis

Average Input

Assume:

Input elements are randomly ordered.

On average:

Each element compares with half of the sorted portion.

Thus:

t_j \approx \frac{j}{2}

Result

The average-case running time still becomes quadratic:

T(n)=\Theta(n^2)

although with a smaller constant factor than the worst case.

11. Best vs Average vs Worst Case

Case	Condition	Complexity
Best	Already sorted	$\Theta(n)$
Average	Random order	$\Theta(n^2)$
Worst	Reverse sorted	$\Theta(n^2)$

12. Why Worst-Case Analysis?

Algorithm analysis usually emphasizes worst-case running time.

Reasons

1. Provides Guaranteed Upper Bound

Worst case guarantees:

Algorithm never exceeds this time.

2. Worst Case Often Occurs

Example:

Searching for absent elements
Reverse-ordered inputs

3. Average Case Often Similar

Even average-case insertion sort remains:

\Theta(n^2)

13. Order of Growth

To simplify analysis:

Ignore constants
Ignore lower-order terms

Focus only on dominant growth.

Example

Suppose:

T(n)=3n^2+5n+10

For large $n$ :

$n^2$ dominates

Thus:

T(n)=\Theta(n^2)

Why Ignore Constants?

As $n$ becomes very large:

Constants become insignificant.

Example:

100n^2

and

n^2

have the same asymptotic growth.

Conclusion

The analysis of insertion sort demonstrates the fundamental methodology used in algorithm analysis. Using the RAM model, we count primitive operations and express running time as a function of input size.

Insertion sort exhibits:

Linear best-case complexity
Quadratic average and worst-case complexity

Through this example, students learn:

How algorithms are mathematically analyzed
How asymptotic complexity is derived
Why worst-case analysis is important
How order of growth determines scalability