Question: An algorithm takes 0.5 ms for input size 100. How long it will take for input size 500 if running time is i) Quadratic ii) NLog N
0

Subject: Analysis Of Algorithm

Topic: Introduction To Analysis Of Algorithm

Difficulty: Medium

aoa(14) • 1.4k views
ADD COMMENTlink
modified 15 months ago  • written 18 months ago by gravatar for satishmanje93 satishmanje9310
0

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.

ADD COMMENTlink
modified 15 months ago  • written 15 months ago by gravatar for satishmanje93 satishmanje9310
Please log in to add an answer.