Time Complexity

Links to this page
Edit this page
Entry portal
Advice For New Users

Prev: What Is A Problem? / Next: What is P?

Time complexity

Remember that a problem is really a collection of instances.
The Time Complexity of an algorithm is a measure of how long it will take. The problem is that two instances of (more or less) the same size can take wildly differing times to solve. For example, 1000000000 is completely trivial to factor, but 1000000013 is quite hard.

So what do we mean when we talk about "the time to solve"?

For a given instance of a problem, we have a concept of its "size," usually expressed as the number of bits required to choose this instance from among all possible instances.

As the size of the instance grows, the algorithm can (quite reasonably) be expected to take longer, and the time complexity tells you what this function looks like.

Specifically, we talk about an upper bound. We find a function F such that for a given number of bits b, the time T(b) taken by the algorithm for any instance I of size less than or equal to b is less than or equal to F(b).
In brief, we want to know how long things will take. We ask for a function, F, such that if you give me an instance of size at most b, the algorithm will be finished in time at most F(b).

F tells us the maximum time we need to wait for a solution.

Described like that, we can see that the time complexity is specific to a particular algorithm, and not necessarily to the problem it solves. However, we can say that the time complexity of a particular problem is "bounded above" by a function because we know of an algorithm that achieves that bound. For example, we know that the time complexity of multiplying two numbers (of size n and m respectively) is bounded above by amn, where a is some constant, because we know that the traditional tried and tested long multiplication algorithm takes (at most) that many steps.

See http://en.wikipedia.org/wiki/Toom-Cook_multiplication
In fact there are faster algorithms for multiplication, and in general, for any given algorithm it's hard to know if there's another, even faster one. As such we usually say that the time complexity of a problem is that of the fastest known algorithm, although this terminology is imprecise and occasionally misleading.

Proven lower bounds can be hard to come by.

Of course, sometimes we don't care about the details and we just want a broad indication of how bad things get. That's where we start talking about classes of algorithms, and, by implication, classes of problems.

One such class is called P.

Prev: What Is A Problem? / Next: What is P?
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout