[Introduction to Algorithms, CLRS] Exercise 1.2-3

알고리즘

[Introduction to Algorithms, CLRS] Exercise 1.2-3

nevermet 2017. 8. 15. 12:31

This is a solution for Introduction to Algorithms. I write this for my study purpose.

1.2-3

What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine?

Answer:

A (quadratic time complexity) will run much faster than B (exponential time complexity) for very large values of n. Let’s start checking from n=1 and go up for values of n which are power of 2.

$n = 1 \Rightarrow 100 \times 1^{2} = 100 > 2^{1}$ $n = 2 \Rightarrow 100 \times 2^{2} = 400 > 2^{2}$ $n = 4 \Rightarrow 100 \times 4^{2} = 1600 > 2^{4}$ $n = 8 \Rightarrow 100 \times 8^{2} = 6400 > 2^{8}$ $n = 16 \Rightarrow 100 \times 16^{2} = 25600 < 2^{16}$

Somewhere between 8 and 16, A starts to run faster than B. Let’s do what we were doing but now we are going to try middle value of the range, repeatedly (binary search).

$n = \frac{8 + 16}{2} = 12 \Rightarrow 100 \times 12^{2} = 14400 > 2^{12}$ $n = \frac{12 + 16}{2} = 14 \Rightarrow 100 \times 14^{2} = 19600 > 2^{14}$ $n = \frac{14 + 16}{2} = 15 \Rightarrow 100 \times 15^{2} = 22500 < 2^{15}$

So, at $n = 15$ , A starts to run faster than B.

source: https://atekihcan.github.io/CLRS/E01.02-03/

저작자표시