Complexity

Comparisons

Sample Functions

Clear[linear, quadratic, power];

linear[n_]:=n

quadratic[n_]:=(n^2)

power[n_]:=(2^n)

Log vs. Linear

Table[Log[2,k],{k,100000.,1000000.,100000}]

Table[linear[k],{k,100000,1000000,100000}]

Plot[{Log[2,t],linear[t]},{t,1,50},PlotStyle->Thickness[.01]]

Quadratic vs. Power

Table[quadratic[k],{k,10,100,10}]

Table[power[k],{k,10,100,10}]

Plot[{quadratic[t],power[t]},{t,1,10},PlotStyle->Thickness[.01]]

nLog(n) vs. Quadratic

Table[k Log[2,k],{k,10.,1000.,100}]

Table[quadratic[k],{k,1000,10000,1000}]

Plot[{t Log[2,t],quadratic[t]},{t,1,10},PlotStyle->Thickness[.01]]

Linear vs. nLog(n)

Table[k Log[2,k],{k,10.,1000.,100}]

Table[linear[k],{k,1000,10000,1000}]

Plot[{linear[t],t Log[2,t]},{t,1,10},PlotStyle->Thickness[.01]]