PROGRAM REQUIREMENTS

Write a program that calculates the performance statistics for n = 30 and n = 1000. For each item write an actual for loop that corresponds to the BigO requested and has the loop count the number of iterations. O(1) would not actually be a loop, but a single statement.

A function using an algorithm with a worst-case running time of O (1).

A function using an algorithm with a worst-case running time of O (n).

A function using an algorithm with a worst-case running time of O (n²).

A function using an algorithm with a worst-case running time of O (n³).

A function using an algorithm with a worst-case running time of O (log₂ n).

A function using an algorithm with a worst-case running time of O (n log₂ n).

A function using an algorithm with a worst-case running time of O (n² log₂ n).

Each function should calculate the performance statistics for its algorithm by having a counter embedded in the function to count the number of times the innermost instruction is executed. The output should report performance at n = 30 and n = 1000 for all seven functions. Put the output into a tabular format with the columns n=30 and n=1000 and the rows each of the BigO functions (similar to below).

n=30 n=1000

O(1) xxxx xxxx

O(n) xxxx xxxx

O(n2) xxxx xxxx

O(n3) xxxx xxxx

O (lg n) xxxx xxxx

O (n lg n) xxxx xxxx

O (n2 lg n) xxxx xxxx