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
- 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
- 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
- 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)
- For 1 to size_of(x):
- return y
- 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)
- 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.
