PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Low Entry average rating: No information on entry rating
time complexity (Definition)

Time Complexity

Time complexity refers to a function describing how much time it will take an algorithm to execute, based on the parameters of its input. The exact value of this function is usually ignored in favour of its order, expressed in the so-called Big-O notation (this is based on the limit of the time complexity function as the values of its parameters increase without bound.)

Complexity classes are equivalence classes of time complexities which are “equal” in Big-O notation. Further, there are meta-complexity classes 1 of time complexities which have Big-O expressions that differ only by some specific parameter. For instance, $ O(n^2)$ and $ O(n^3)$ are both polynomial time complexity classes, similarly $ O(2^n)$ and $ O(3^n)$ are exponential time complexity classes.

Example

All comparison-based sorting has time complexity no better than $ O(n \log n)$, where $ n$ is the number of elements to be sorted. The exact expression for time complexity of a particular sorting algorithm may be something like $ T(n)= a n \log n + b$, with $ a$ and $ b$ constants, which still is order $ O(n \log n)$.


Footnotes

... classes1
This term has been invented for use in this entry.


"time complexity" is owned by akrowne.
(view preamble)

View style:

Also defines:  polynomial time, polynomial-time, exponential time, exponential-time, complexity classes, meta-complexity classes
Log in to rate this entry.
(view current ratings)

Cross-references: expressions, big-o, term, equivalence classes, bound, limit, big-O notation, order, parameters, algorithm, function
There are 26 references to this entry.

This is version 5 of time complexity, born on 2001-10-18, modified 2005-04-18.
Object id is 309, canonical name is TimeComplexity.
Accessed 15522 times total.

Classification:
AMS MSC: 68Q15 (Computer science :: Theory of computing :: Complexity classes )
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)