Classfying Mathematic & Timing Functions

by Jeff Hunter, Sr. Database Administrator

Timing Functions Overview

T(n)	10	100	1,000	10,000
log n	3	6	9	13
n1/2	3	10	31	100
n	10	100	1,000	10,000
n log n	30	600	9,000	130,000
n2	100	10,000	1,000,000	100,000,000
n3	1,000	1,000,000	1,000,000,000	1,000,000,000,000
2n	1,024	1030	10300	103000

NOTE: There is approximately 10⁵⁰ particles in the universe today.

Mathematical Functions

Constant	5
Logarithmic	5 log n
Poly Logarithmic	(log n)5
Polynomial	n5
Exponential	25n
Exp	2n5
Double Exp	225n

Polynomial Functions

Linear	5n
Quadratic	5n2
Cubic	5n3
?	5n4

Defining Mathematical Functions

• Which Functions are Quadratic?

  n²
  0.001 n²
  5n² + 3n + 2log n
  1000 n²
  

  Some constant times n².
  Ignore low-order terms.
  Ignore multiplicative constants.
  Ignore "small" values of n.
  Write T(n2).

• Which Functions are Polynomial?

  n^c
  n^0.0001
  5n² + 8n + 2log n
  5n² log n
  5n^2.5
  n¹⁰⁰⁰⁰
  

  n to some constant power.
  Ignore low-order terms.
  Ignore power constant.
  Ignore "small" values of n.
  Write n^T(1)
  

• Which Functions are Exponential?

  2ⁿ
  2^{0.0001 n}
  8ⁿ
  2ⁿ / n¹⁰⁰
  2ⁿ * n¹⁰⁰
  2^{10000 n}
  

  n times some constant power raises to the power of 2.
  Ignore base.
  Ignore constant in front of n.
  Ignore "small" values of n.
  Ignore polynomial factors.
  Write 2^T(n)