**Introduction:**

- Complexity Theory deals with how ‘complex’ a problem is to solve. That is, how many steps it takes to solve a problem.

- This topic is one of the most profound and consequential topics in all of computer science and mathematics.

**Big-O Notation:**

- Big-O notation is a notation that computer scientists use to describe the complexity of algorithms. This notation helps to describe how many steps an algorithm will take to complete a task at runtime.

- Big-O notation attempts to capture these algorithms “scale” (i.e. their growth rate) as the problem sizes growth.

- Types:
- O(1) – Constant
- O(n) – Linear
- O(log(n)) – Logarithmic
- O(n2) – Quadratic
- O(n3) – Cubic
- O(n^c) – Polynomial, C is a constant
- O(c^n) – Exponential , C is a constant
- O(n!) – Factorial

**Example O(1):**

- function foo(int x):
- x = x + 1
**(step 1)** - return x

- x = x + 1

- The function ‘foo’ has Big-O of O(1) runtime, since no matter how big the input x is, it always takes the same number of steps (or amount of time) to compute things.

**Example O(1)**:

- function foo(int x):
- x = x + 1
**(step 1)** - y = x + 1
**(step 2)** - z = x + 1
**(step 3)** - return x

- x = x + 1

- The function ‘foo’ has Big-O of O(1) runtime, since no matter how big the input x is, it always takes the same number of steps (or amount of time) to compute things.

**Note: Even though this is technically O(3) runtime, this is also equivalent to O(1) runtime. This is because O(1) and O(3) both have an equivalent growth rate; that is constant. Therefore, we usually just say this function has a O(1) runtime. (i.e. O(3) = O(1) = O(C), where C is a constant Integer).**

**Notice how this would still be a constant runtime even if we add more arbitrary steps because the number of steps does not increase based on the input size.**

**Example O(n):**

- function foo(int x):
- y = 1 (step 1)
- For 1 to size_of(x):
- y = y + 1
**(steps 2 to n+1)** - return y

- The function ‘foo’ has a Big-O of O(n) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things will scale linearly with x.

**Note: Even though this is technically O(n + 1) runtime, this is also equivalent to O(n) runtime. This is because O(n+1) and O(n) both have an equivalent growth rate; that is linear. Therefore, we usually just say this function has a O(n) runtime. (i.e. O(n+1) = O(n) = O(n + C), where C is a constant Integer).**

**Example O(n)**:

- function foo(int x):
- y = 1
**(step 1)** - z = 1
**(step 2)** - For 1 to size_of(x):
- y = y + 1
**(step 3 to n+2)** - For 1 to size_of(x):
- z = z + 1
**(step n+3 to 2n+2)** - return y, z

- y = 1

- The function ‘foo’ has a Big-O of O(n) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things will scale linearly with x.

**Note: Even though this is technically O(2n+2) runtime, this is also equivalent to O(n) runtime. This is because O(2n+2) and O(n) both have an equivalent growth rate; that is constant. Therefore, we usually just say this function has a O(n) runtime. (i.e. O(2n+2) = O(n) = O(Bn+C), where B & C is are constant integers).**

**Notice how this would still be a linear runtime even if we add more non-nested for loops because the number of steps does not increase based on the input size.**

**Example O(n^2)**:

- function foo(int x):
- y = 1
**(step 1)** - For 1 to size_of(x):
- For 1 to size_of(x):
- y = y + 1
**(steps 2 to n^2+1)**

- y = y + 1

- For 1 to size_of(x):
- return y

- y = 1

- The function ‘foo’ has a Big-O of O(n^2) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things is will scale quadradically with x.

**Example O(n** **^** **3)**:

- function foo(int x):
- y = 1 (step 1) (step 1)
- For 1 to size_of(x):
- For 1 to size_of(x):
- For 1 to size_of(x):
- y = y + 1 (steps 2 to n
**^**3+1)

- y = y + 1 (steps 2 to n

- For 1 to size_of(x):

- For 1 to size_of(x):
- return y

- The function ‘foo’ has a Big-O of O(n
**^**3) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things is will scale cubically with x.

**Example O(n^c):**

- function foo(int x):
- y = 1 (step 1) (step 1)
- For 1 to size_of(x):
- For 1 to size_of(x):
- For 1 to size_of(x):
- ……
- …….
- ….…….
- y = y + 1 (steps 2 to n^c+1)

- ….…….

- …….

- ……

- For 1 to size_of(x):

- For 1 to size_of(x):
- return y

- The function ‘foo’ has a Big-O of O(n^c) runtime, because depending on how big the input x is, the number of steps (or amount of time) to compute things is will scale to the power of c with x.

**Complexity Classes:**

- In general, algorithms that have a polynomial runtime or lower are considered computationally friendly, and can be solved in a reasonable amount of time by a computer due to scaling polynomially. The class of problems that can be solved by deterministic polynomial runtime algorithms are known as the P-class problems. In other words, they are
**Polynomial-time problems**that belong to the polynomial-time complexity class.

- In contrast, algorithms that have an exponential runtime, prove to be very computationally challenging for computers as they scale. Computers often cannot solve these in a reasonable amount of time because they scale exponentially. This class of problems that required algorithms with exponential or greater runtimes are known as NP-hard class problems. Here, NP stands for
**Nondeterministic Polynomial-Time Problems.**This essentially means that if we could search all paths of the problem at one time (simultaneously), we could find a polynomial-time solution.

**NP-Complete class problems**are a subclass of NP-Hard problems and a subclass of NP problems (however: NP class ≠ NP-Hard class) for which it is difficult to find a solution (takes an exponential time algorithm) but if the solution is known, if can be verified in Polynomial-time (by a polynomial-time algorithm). The de facto NP-Complete problem is SAT. It is very easy to verify a solution once it’s given, but it is very hard to find a solution. NP-Complete problems are the hardest problems in the NP class. In fact, if a Polynomial-time algorithm is found (none have been found yet) to solve an NP-Complete problem, then all NP problems can be solved using it.

**NP class problems sit in between P and NP-Complete class problems and are a class of problems that can be reduced to NP-Complete problems (such as a being converted to a SAT problem) by a polynomial-time**algorithm.

**coNP class problems**are a subclass of NP-Hard problems which, rather than being easy to verify a solution, it is easy to exclude non-solutions. In other words, you can exclude non-solutions in polynomial time. The de facto coNP-Complete problem is UNSAT (proving that a Boolean formula is unsatisfiable).

**coNP-Complete class problems**are the hardest problem in coNP. coNP problems are both NP-hard and coNP.

- Every once in a while we find an efficient polynomial time algorithm for a problem in NP, and realize that it is actually a P problem; we just never realized it.

- This leads us to one of the biggest unsolved questions in all of computer science and mathematics is:
- P = NP? Or P ≠ NP?

- If P = NP, then all of the NP-Complete & coNP-Complete problems (including SAT/UNSAT) are really P problems, and many of the computational challenges we have today will disappear.

- The general suspicion is that P ≠ NP, but no one has been able to prove it.