Körtider

¶

Antal indata är nVi kallar den sökta körtiden x1. Linjär tid innebär att T(n) = k*nFör n=100 tar algoritmen 0.5 ms, alltsåk*100 = 0.5För n=500 tar algoritmen x ms, alltsåk*500 = xLö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.5Fö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.5Fö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.

¶