Körtider

Antal indata är \(n\)
Vi kallar den sökta körtiden \(x\)

1. Linjär tid innebär att \(T(n) = k*n\)
För \(n=100\) tar algoritmen 0.5 ms, alltså
$$k*100 = 0.5$$
För \(n=500\) tar algoritmen x ms, alltså
$$k*500 = x$$
Löser vi ut \(x\) får vi 2.5 ms dvs 5 gånger så lång tid.

2. \(O(n\log_{}n)\) innebär att \(T(n)=k*n\log_{}n\)

För \(n=100\) tar algoritmen 0.5 ms, alltså
$$k*100*\log_{}100 = 0.5$$
För \(n=500\) tar algoritmen x ms, alltså
$$k*500*\log_{}500 = x$$

$$x=0.5*\frac{500\log_{}500}{100\log_{}100}$$
Löser vi ut \(x\) får vi 3.4 ms dvs ca 6 gånger så lång tid.

3. Kvadratisk tid innebär att \(T(n)=k*n^{2}\)

För \(n=100\) tar algoritmen 0.5 ms, alltså
$$k*100^{2} = 0.5$$
För \(n=500\) tar algoritmen x ms, alltså
$$k*500^{2} = x$$

$$x=0.5*\frac{500^{2}}{100^{2}}$$
Löser vi ut \(x\) får vi 12.5 ms dvs 25 gånger så lång tid.