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.
4. Kubisk tid innebär att \(T(n)=k*n^{3}\)
För \(n=100\) tar algoritmen 0.5 ms, alltså
\(k*100^{3} = 0.5\)
För \(n=500\) tar algoritmen x ms, alltså
\(k*500^{3} = x\)
\(x=0.5*\frac{500^{3}}{100^{3}}\)
Löser vi ut \(x\) får vi 62.5 ms dvs 125 gånger så lång tid.
