Data Structures and Algorithms |
No Title
[an error occurred while processing this directive]by Jeff Hunter, Sr. Database Administrator
T(n)
10
100
1,000
10,000
log n
3
6
9
13
n^{1/2}
3
10
31
100
n
10
100
1,000
10,000
n log n
30
600
9,000
130,000
n^{2}
100
10,000
1,000,000
100,000,000
n^{3}
1,000
1,000,000
1,000,000,000
1,000,000,000,000
2^{n}
1,024
10^{30}
10^{300}
10^{3000}
NOTE: There are approximately 10^{50} particles in the universe today.
Constant
5
Logarithmic
5 log n
Poly Logarithmic
(log n)^{5}
Polynomial
n^{5}
Exponential
2^{5n}
Exp
2^{n5}
Double Exp
2^{25n}
Linear
5n
Quadratic
5n^{2}
Cubic
5n^{3}
?
5n^{4}
Which Functions are Quadratic?
n^{2}
0.001 n^{2}
5n^{2} + 3n + 2log n
1000 n^{2}
Some constant times n^{2}
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^{2} + 8n + 2log n
5n^{2} log n
5n^{2.5 }
n^{10000}
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^{n}
2^{0.0001 n}
8^{n}
2^{n} / n^{100}
2^{n} * n^{100}
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)}
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 server environment. Jeff's other interests include mathematical encryption theory, tutoring advanced mathematics, 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 20 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 and Mathematics.
Copyright (c) 1998-2017 Jeffrey M. Hunter. All rights reserved.
All articles, scripts and material located at the Internet address of http://www.idevelopment.info is the copyright of Jeffrey M. Hunter and is protected under copyright laws of the United States. This document may not be hosted on any other site without my express, prior, written permission. Application to host any of the material elsewhere can be made by contacting me at jhunter@idevelopment.info.
I have made every effort and taken great care in making sure that the material included on my web site is technically accurate, but I disclaim any and all responsibility for any loss, damage or destruction of data or any other property which may arise from relying on it. I will in no case be liable for any monetary damages arising from such loss, damage or destruction.
Last modified on
Thursday, 16-Sep-2010 22:29:56 EDT
Page Count: 2300