written 3.6 years ago by | • modified 3.3 years ago |

**Subject:** Analysis Of Algorithm

**Topic:** Introduction To Analysis Of Algorithm

**Difficulty:** Medium

**1 Answer**

0

5.0kviews

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

written 3.6 years ago by | • modified 3.3 years ago |

**Subject:** Analysis Of Algorithm

**Topic:** Introduction To Analysis Of Algorithm

**Difficulty:** Medium

ADD COMMENT

0

133views

written 3.3 years ago by | • modified 3.3 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.

ADD COMMENT

Please log in to add an answer.