Data Structures and Algorithms

Classfying Mathematic and Timing Functions

by Jeff Hunter, Sr. Database Administrator

Contents

• Introduction
• Timing Functions Overview
• Mathematical Functions
• Polynomial Functions
• Defining Mathematical Functions
• About the Author

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 are 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)
  

About the Author

Jeffrey Hunter is an Oracle Certified Professional, Java Development Certified Professional, Author, and an Oracle ACE. Jeff currently works as a Senior Database Administrator for The DBA Zone, Inc. located in Pittsburgh, Pennsylvania. His work includes advanced performance tuning, Java and PL/SQL programming, developing high availability solutions, capacity planning, database security, and physical / logical database design in a UNIX, Linux, and Windows server environment. Jeff's other interests include mathematical encryption theory, programming language processors (compilers and interpreters) in Java and C, LDAP, writing web-based database administration tools, and of course Linux. He has been a Sr. Database Administrator and Software Engineer for over 18 years and maintains his own website site at: http://www.iDevelopment.info. Jeff graduated from Stanislaus State University in Turlock, California, with a Bachelor's degree in Computer Science.