Exercise I

  • Use Big-Oh notation to describe the asymptotic running time of a program given its precise running time as a function of input size.

Assume that each of the expressions below gives the processing time T(n)T(n) spent by an algorithm for solving a problem of size nn. Specify the asymptotic running time in Big-Oh notation.

Exercise T1(n)=5+0.001n3+0.025nT_1(n) = 5 + 0.001n^3 + 0.025n

Solution

The dominant term is n3n^3, so the runtime is O(n3)\Omicron(n^3).

Exercise T2(n)=3lg⁡n2+(lg⁡n)2+(n+1)2lg⁡(4n)T_2(n)=3\lg n^2+(\lg n)^2 + (n+1)^2\lg (4n)

Solution

Let's simplify the expression; this requires a certain level of mathematical literacy. Most of what is done below are based on the laws of logarithms.

=3×2lg⁡n+lg⁡2n+(n2+2n+1)(lg⁡4+lg⁡n) = 3\times 2\lg n + \lg^2 n + (n^2 + 2n + 1)(\lg 4 + \lg n)

=6lg⁡n+lg⁡2n+(n2+2n+1)(2+lg⁡n) = 6\lg n + \lg^2 n + (n^2+2n+1)(2+\lg n)

=6lg⁡n+lg⁡2n+2n2+4n+2+n2lg⁡n+2nlg⁡n+2lg⁡n = 6\lg n + \lg^2 n + 2n^2 + 4n + 2 + n^2\lg n + 2n\lg n + 2\lg n

=n2lg⁡n+2n2+2nlg⁡n+4n+lg⁡2n+8lg⁡n+2 = n^2\lg n + 2n^2 + 2n\lg n + 4n + \lg^2 n + 8\lg n + 2

The dominant term is n2lg⁡nn^2\lg n, so the runtime is O(n2lg⁡n)\Omicron(n^2\lg n).

Note, lg⁡n\lg n is log⁡2n\log_2 n and n2lg⁡nn^2\lg n is larger than 2n22n^2 for all n>4n > 4.

You might be wondering how I know which term has the highest order (fastest rate of growth). This, again, requires a certain level of mathematical literacy. However, a dozen functions show up in most practical cases, and we will survey them in a later lesson.