Runtimes and Complexity Demo

Example 1: Computing a sum

The following module computes f(n)=(∑_(i=1)^n)i.

example1[n_]:=Module[
{total=0},
(* loop: i from 1 to n*) 
Do[
total +=i
,{i,1,n}];
(* return value *) 
total
]

nVals1=Range[100000,2000000,100000];
ClearSystemCache[];
runtimes1=Monitor[Table[{n,Timing[example1[n]][[1]]},{n,nVals1}],n]

Plot the runtimes:

ListPlot[runtimes1,AxesLabel->{"n","runtime (seconds)"}]

Example 2: Computing a double sum

The following module computes f(n)=(∑_(i=1)^n)(∑_(j=1)^n)i·j.

example2[n_]:=Module[
{total=0},
(* loop: i from 1 to n, j from 1 to n *)
Do[
total += i*j
,{i,1,n},{j,1,n}];
(* return value *) 
total
]

nVals2=Range[500,5000,500];
ClearSystemCache[];
runtimes2=Monitor[Table[{n,Timing[example2[n]][[1]]},{n,nVals2}],n]

Plot the runtimes:

ListPlot[runtimes2,AxesLabel->{"n","runtime (seconds)"}]

Example 3: The selection sort algorithm

The following module implements the selection sort algorithm for sorting a list:

sortList[list_]:=Module[
{n=Length[list],vals=list,jMin},

(* loop: i from 1 to n *)
Do[
(* find the smallest element in position i through the end of the list *)
jMin=i;
Do[
(* if this element is smaller than the number at jMin, then it is the new minimum *)
If[vals[[j]]<vals[[jMin]],
(* found new minimum; remember its index *)
jMin=j
]
,{j,i+1,n}];
(* swap elements with indexes i and jMin *)
If[jMin!=i,
{vals[[i]],vals[[jMin]]}={vals[[jMin]],vals[[i]]}
]
,{i,1,n}];
(* return the sorted list *) 
vals
]

Test the sorting algorithm:

testList=RandomSample[Range[10]]
sortedList=sortList[testList]

Now let’s write a module to generate a random list of length n and measure the time required to sort it.

timeSort[n_]:=Module[
{nums,time},
(* generate a random list of length n *)
nums=RandomSample[Range[n]];
(* measure the runtime required to sort the list *) 
ClearSystemCache[];
time=Timing[sortList[nums]][[1]];
(* return the runtime *) 
time
]

Try out the runtime module:

timeSort[1000]

Now measure runtimes for sorting a bunch of lists:

nVals3=Range[100,2000,100];
runtimes3=Monitor[Table[{n,Timing[timeSort[n]][[1]]},{n,nVals3}],n]

Plot the runtimes:

ListPlot[runtimes,AxesLabel->{"n","runtime (seconds)"}]

Example 4: built-in sorting algorithm

This module generates a random list of length n and measure the time required to sort it using Mathematica’s Sort function.

timeBuiltInSort[n_]:=Module[
{nums,time},
(* generate a random list of length n *)
nums=RandomSample[Range[n]];
(* measure the runtime required to sort the list *) 
ClearSystemCache[];
time=Timing[Sort[nums]][[1]];
(* return the runtime *) 
time
]

Try out the runtime module:

timeBuiltInSort[10000000]

Now measure runtimes for sorting a bunch of lists:

nVals4=
runtimes4=Monitor[Table[{n,Timing[timeBuiltInSort[n]][[1]]},{n,nVals4}],n]

Plot the runtimes:

ListPlot[runtimes,AxesLabel->{"n","runtime (seconds)"}]