Subject: Analysis Of Algorithm

Topic: Introduction To Analysis Of Algorithm

Difficulty: Medium

Running time: It is a simple sorting algorithm that works well with small or mostly sorted data. However, it takes a long time to sort large unsorted data. To see why, we will analyze its running time. Running Time of Algorithm is the running time of analgorithm for a specific input depends on the number of operations executed. Given:

i) Quadratic
For N = 100 input size

∴ N^2 = 10000 steps and running time is 0.5 ms.

For N = 500 input size

∴ N^2 = 250000 steps are required and running time is

(250000*0.5)/10000 = 12.5 ms is required running time for execution.

ii) )O(N Log N)

For N = 100 input size

Log N = 6.65

∴ N Log N = 665

For 665 instructions 0.5 ms is required running time

If N Log N = 500 N 500 = 4483 instructions

So the required time is (4483 * 0.5)/665 = 3.37 ms.