CS 3343/3341
 Analysis of Algorithms 
  Hierarchy of Problems   

A Hierarchy of Increasingly Difficult Problems:

We are considering computational problems with input size proportion to a variable n. Usually we are interested in worst-case time performance, or failing that in average-case time performance. We may also sometimes be interested in the amount of space (memory) a problem requires. Mostly we will be interested in upper bounds for the performance, and often tight upper bounds if we can obtain them. Lower bounds are also of great interest, but it is usually not possible to prove such bounds. We are rarely interested in best-case performance.

Keep in mind that a given problem may have a number of algorithms that solve it, with differing performance. Thus we can talk about the difficulty of an algorithm, or the inherent difficulty of a problem, that is, what is the best you can do on the problem with any algorithm.

Here are some big-O or big-Θ bounds, with a corresponding algorithm afterwards:

ClassName Time for n=100 Examples and Comments
O(1)Constant
time		1 Hash-table look-up.
O(log(log(n)))Double
logarithmic		 2.7Interpolation search.
O(log(n)) Logarithmic6.6 Binary search, or algorithms that halve the input size at each step. These cannot examine all of their input or else they would be at least linear.
O(√n) Square root10 Prime testing, where you check for divisors up to √n.
O(n)Linear100 Algorithms that go through a list of size n, such as linear search.
O(n*log(n))n-log-n660 High performance sorts.
O(n2) Quadratic10000 Low-performance sorts, matrix addition, any use of doubly-nested loops.
O(n3) Cubic1000000 Ordinary matrix multiplication, triply-nested loops.
O(n8) Polynomial1016 Artificial problems, such as adding 8-dimensional matrices
The class P Polynomial-
time		Not too
large		 O(nk), for some fixed k. Rarely is k greater than 4
The class NP
of problems		 Most likely
P != NP		Small and
large		 These are algorithms that can be verified in polynomial time
NP-Complete
problems		 The hardest
in NP		Probably
large		 These might also be in P, but likely not, though nobody knows. This is a large class of optimization problems that are important in many areas.
O(2n) Exponential2100 ≐
1.267e30		 Sometimes problems that look at all subsets
O(n!)Factorial100! ≐
9.33e157		 Sometimes problems that look at all permutations
O(222 ...2n) IntractableUnimaginable Some problems require more time than this for any finite number of 2s, such as deciding if an extended regular expression defines the empty set.
Undecidable
problems		 Have no
solution		+∞ Also called unsolvable problems. These are problems that cannot be solved by any algorithm or machine or model of computation known to humans.

Revision date: 2012-05-29. (Please use ISO 8601, the International Standard Date and Time Notation.)