Limitations of Complexity

Question 1

What is Big-O notation?

Answer 1

A notation that expresses computing complexity as the term in a function that increases most rapidly, relative to the size of a problem.

Question 2

What is the Big-O notation used to describe?

Answer 2

The upper bound of a algorithm’s complexity. The longest time it would take to execute/complete an algorithm.

Question 3

What is the order of magnitude for Big-O notation?

Answer 3

• O(1)
• O(log2(N))
• O(N)
• O(N log2 N)
• O(N^2)
• O(N^C)
• O(C^N)
• O(n!)

Question 4

What are polynomial time algorithms?

Answer 4

Algorithms whose order of magnitude can be expressed as polynomial in the size of the problem.

Question 5

What is Polynomial time complexity (P)?

Answer 5

Problems that can be solved with a deterministic processor in polynomial time?

Question 6

What is nondeterministic polynomial (NP)?

Answer 6

Problems that can be solved with a nondeterministic processor in polynomial time but can be verified by a deterministic processor in polynomial time.

Question 7

What are NP-hard problems?

Answer 7

Problems which are at least as hard to solve as NP problems, but where the solution may not be verifiable in polynomial time?

Question 8

What are Np-Complete problems?

Answer 8

The hardest problems to solve in the NP class. Proving that any of the NP-Complete problems can be solved in polynomial time would mean that all NP problems could be.