Computational complexity theory notes
Jump to navigation
Jump to search
✎ This article/section is a stub — some half-sorted notes, not necessarily checked, not necessarily correct. Feel free to ignore, or tell me about it.
Note that this page will be informal, it is meant to introduce the basic ideas, and leave the the harder math to those actually interested. If you want to understand this more thoroughly, get a book or go to university:)
Note also that there are other things named complexity theory[1]. This is the one about categories of computational problems.
Introduction
Complexity theory...
- deals not with exactly how many operations or execution time is needed, but with how fast execution time increases with increasing problem size
- largely to allow comparison between (classes of) algorithms in terms of efficiency
- can analyse algorithms for best, worst and average case of input (can be a useful distinction)
- uses complexity classes to organize problems and solutions into classes of decidability and solvability
Complexity theory is useful to tell you
- how fast computation will get out of hand,
- when you want to know whether there is a better class of algorithm to solve a problem you have,
- places where inexact estimations may help you structurally rather than barely
tl;dr
Some useful concepts
The basic operation
small enough / large enough n
Discarding lower order things
Equal complexity
Running times and their names
Worst, average and best case; amortized analysis
✎ This article/section is a stub — some half-sorted notes, not necessarily checked, not necessarily correct. Feel free to ignore, or tell me about it.
Big-O and little-o
✎ This article/section is a stub — some half-sorted notes, not necessarily checked, not necessarily correct. Feel free to ignore, or tell me about it.
Θ (Theta)
Ω (Omega)
ω (omega)
complexity classes
Some of the common classes
Commonly mentioned:
P and NP
NP-complete (NP-C, NPC)
NP-hard
See also (complexity classes)
Some other details
Less usual
✎ This article/section is a stub — some half-sorted notes, not necessarily checked, not necessarily correct. Feel free to ignore, or tell me about it.