written 6.7 years ago by | modified 2.7 years ago by |
Subject: Analysis Of Algorithm
Topic: Introduction To Analysis Of Algorithm
Difficulty: Medium
written 6.7 years ago by | modified 2.7 years ago by |
Subject: Analysis Of Algorithm
Topic: Introduction To Analysis Of Algorithm
Difficulty: Medium
written 6.5 years ago by | • modified 6.5 years ago |
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.