{"id":266,"date":"2007-01-07T21:05:44","date_gmt":"2007-01-07T21:05:44","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/01\/07\/basic-computational-complexity\/"},"modified":"2015-04-26T15:30:52","modified_gmt":"2015-04-26T19:30:52","slug":"basic-computational-complexity","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/01\/07\/basic-computational-complexity\/","title":{"rendered":"Basic Computational Complexity"},"content":{"rendered":"

In the comments thread of the post on Turing Equivalent vs Turing Complete<\/a>, there’ve been a flurry of questions and comments about some stuff involving computational complexity. So I thought it would be interesting to write a couple of posts about computational complexity. I’m not going to get into a lot of detail, because I would need to dig out some books that I really<\/em> don’t want to read again :-). But I can do the basics without them. It’ll take a few posts to get through this.<\/p>\n

<\/p>\n

The logical place to begin is: What is computational complexity? When we look at a computation, one of the things we want to know is: “How long will this take?”. A specific concrete answer to that depends on all sorts of factors – the speed of your computer, the particular programming language you use to run the program, etc. But independent of those, there’s a basic factor that describes something important about how long a computation will take – the algorithm itself fundamental requires some minimum number of operations. Computational complexity is an abstract method of describing how many operations a computation will take, expressed in terms of the size or magnitude of the input.<\/p>\n

When we talk about complexity, we can talk about two different kinds<\/em> of complexity: the complexity of an algorithm<\/em>, and the complexity of a problem<\/em>. The complexity of an algorithm is a measure of how many steps the algorithm takes to execute on an input of a particular size. It’s specific to the algorithm<\/em>, that is, the specific method used to solve the the problem. The complexity of the problem<\/em> is a bound that bounds the best case<\/em> of the complexity of any possible algorithm<\/em> that can solve that problem.<\/p>\n

For example, if you want to sort a list of names, you need to compare names to figure out where things go in the sorted list. If you think about any sorting algorithm, it’s also pretty obvious that in terms of execution, the time it takes to run a sorting algorithm is overwhelmingly dominated by time it takes to do the comparisons.<\/p>\n

One of the most popular algorithms for sorting lists is called quicksort<\/em>. In the worst case, quicksort will require a number of steps proportional to the length of the list squared<\/em>; on average, quicksort will require a number of steps proportional to the length of the list times thelogarithm of the length of the list (n × log(n) if n is the length of the list). <\/p>\n

But no matter how clever you are, there is some minimum number of comparisons that you absolutely must<\/em> do in order to produce a properly sorted list no matter what you get as input. In the case of sorting a list of n<\/em> names, that happens to be proportional to n × log(n)<\/em>. <\/p>\n

Talking about complexity the way I did in the previous couple of paragraphs is really pretty awkward. To make it easier to talk about, we have a special notation we use, called big O notation<\/em>. Roughly speaking, when we have an algorithm like sorting where we know that no matter what it’s given as input, for a list of n<\/em> elements, the largest possible<\/em> number of comparisons that are required to sort the list is proportional to n log(n)<\/em>, we say that sorting has a complexity of O<\/b>(n log(n)). Big O is an upper bound<\/em>: it gives an approximation of the maximum number of steps required for the worst possible input<\/em>; nothing will ever be slower than its Big O bound.<\/p>\n

To be precise and formal for a moment, what big O actually means is a little more complicated. Many computations have some basic minimum cost for setting up; and many have some factor dependent on the size of the input that might be dominant for small inputs, but which gets dwarfed as the size of the input grows. We don’t want those factors muddying things up. The formal definition of big O specifically says how we’re going to eliminate those kinds of factors that are really just noise.<\/p>\n

Take a computation C<\/em> with input size n<\/em>. Let’s say that the maximum number of steps required to execute C<\/em> on an input of size n is given by some function k(n). We say that C<\/em> has complexity O<\/b>(f(n)) (or C is<\/em> O<\/b>(f(n))) if\/f:<\/p>\n

∃ n0<\/sub>, M : ∀ n > n0<\/sub>, k(n) ≤ M × f(n)<\/p>\n

\"just-one.jpg\"<\/p>\n

Just to make sure that that’s clear, here’s a quick example to give you the sense of what a big-O bound means. To the right is a log-scale graph of “max(x ln(x)+x,2+x)”, a function which could be the number of instructions needed for a sort algorithm.<\/p>\n

\"two-logs.jpg\"<\/p>\n

Like most good sort algorithms, this is O<\/b>(n lg(n)). But if we just add “x ln x” to the graph
\nin red, then you can see it’s always smaller<\/em> than the original curve. Looking at this naively, you might think that this would mean that we shouldn’t use O<\/b>(n lg(n)) as a bound.<\/p>\n

\"all-three-logs.jpg\"<\/p>\n

But if we multiply it by 2, then starting around 2.5, the log curve (now in blue) overtakes the algorithm curve. Since there is a constant factor (M=2) where beyond some minimum point (n0<\/sub>=2.5), M×(n lg(n)) is always larger than the number of steps needed by the algorithm, then O<\/b>(n lg(n)) is a valid bound.<\/p>\n

Big O is a worst-case measure<\/em>: it tells you that you will never need more than<\/em> a certain number of instructions to complete a computation. It is, in many ways, a blunt instrument. It can’t tell you how many instructions you actually<\/em> need; it can only tell you that it will be less than<\/em> some number. We sometimes use it to compute upper bounds on the average<\/em> number of instructions used by an algorithm.<\/p>\n

We tend to categorize complexity into a particular group of classes. Roughly speaking, we tend to use something like the following taxonomy:<\/p>\n

\n
O<\/b>(1)<\/dt>\n
Constant time – something that takes the same number of steps for any input.<\/dd>\n
O<\/b>(log(n))<\/dt>\n
Logarithmic time – something where the time to compute it is dependent on the logarithm of the size of the input. An example of a log time algorithm is finding a particular value in a sorted list of values where the time to compare two values is constant.<\/dd>\n
O<\/b>(n)<\/dt>\n
Linear time – something that takes time proportional to the length of input. For example, finding a particular value in an unsorted<\/em> list; or comparing two variable length strings.<\/dd>\n
O<\/b>(n log(n))<\/dt>\n
Something that takes time proportional to the length of the input times the log of the length of the input. This one sounds strange and unlikely to a lot of people, but it turns out to be a very common class – as we saw above, it’s the complexity of sorting.<\/dd>\n
O<\/b>(n2<\/sup>)<\/dt>\n
Quadratic time: something whose execution time is proportional to the square<\/em> of the size of the input. For many systems, O<\/b>(n2<\/sup>) is treated as an upper bound on the complexity of any practical computations. For example, many compilers are implemented with the requirement that intra-procedural<\/em> analysis\/optimization be no worse than quadratic.<\/dd>\n
O<\/b>(n3<\/sup>)<\/dt>\n
Cubic time. Another common maximum bound on the complexity of “practical” computations. Cubic is somewhat common as a complexity bound in dynamic programming algorithms. <\/dd>\n
O<\/b>(nk<\/sup>) for any fixed exponent k<\/dt>\n
This is what we call polynomial time<\/em>, or P-time – something bounded by any constant exponent. It’s pretty much universally accepted that only P-time computations are really practical.\n<\/dd>\n
O<\/b>(nf(n)<\/sup>) where f is monotonically increasing in n.<\/dt>\n
Exponential time. The time to perform a computation is bounded by the size of its input raised to a monotonically increasing exponent. This is nightmare territory – things where we’ve got an algorithm that can do the computation in theory, but which is essentially impossible in practice.<\/dd>\n<\/dl>\n","protected":false},"excerpt":{"rendered":"

In the comments thread of the post on Turing Equivalent vs Turing Complete, there’ve been a flurry of questions and comments about some stuff involving computational complexity. So I thought it would be interesting to write a couple of posts about computational complexity. I’m not going to get into a lot of detail, because I […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[54],"tags":[],"class_list":["post-266","post","type-post","status-publish","format-standard","hentry","category-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-4i","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/266","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=266"}],"version-history":[{"count":2,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/266\/revisions"}],"predecessor-version":[{"id":3152,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/266\/revisions\/3152"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=266"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=266"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=266"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}