# 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.