In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input. The time complexity of an algorithm is commonly expressed using big O notation, which excludes coefficients and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity. For example, if the time required by an algorithm on all inputs of size n is at most 5n3 + 3n, the asymptotic time complexity is O(n3).
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation takes a fixed amount of time to perform. Thus the amount of time taken and the number of elementary operations performed by the algorithm differ by at most a constant factor.
Big O notation is used in computer algorithms as a worst-case scenario illustration. Constants are not considered as we are only concerned on how a function f(x) can grow respectively to g(x) in a way so, f(x) = O(g(x))
Since an algorithm's performance time may vary with different inputs of the same size, one commonly uses the worst-case time complexity of an algorithm, denoted as T(n), which is defined as the maximum amount of time taken on any input of size n. Time complexities are classified by the nature of the function T(n). For instance, an algorithm with T(n) = O(n) is called a linear time algorithm, and an algorithm with T(n) = O(2n) is said to be an exponential time algorithm.
Read more about Time Complexity: Table of Common Time Complexities, Constant Time, Logarithmic Time, Polylogarithmic Time, Sub-linear Time, Linear Time, Linearithmic/quasilinear Time, Sub-quadratic Time, Polynomial Time, Superpolynomial Time, Quasi-polynomial Time, Sub-exponential Time, Exponential Time, Double Exponential Time
Famous quotes containing the words time and/or complexity:
“My friend devotes himself to his life, whenever he can find the spare time. His motto is: ‘Don’t just sit there: live!’ So he’s too busy to stand, to walk, to do anything, except to live. He even refused to kiss a girl, when invited, on the grounds that it was time again to be living. Schedules are sacred to him.”
—Marvin Cohen, U.S. author and humorist. The Self-Devoted Friend, New Directions (1967)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)