**AMCAT Computer Programming module:** For AMCAT exam, Quantitative ability, Logical reasoning and English language are the mandatory modules. Apart from that, for IT job aspirants, Computer programming is an essential section. Here we will be discussing in detail about AMCAT Complexity Theory Questions.

**AMCAT Complexity Theory Questions – Computer Programming**

Usually 1-2 questions, come from the topic Complexity Theory. The question level varies from easy to tough. It takes an average of 40 to 50 seconds to solve the problem. Below you will get to know about what is Complexity theory and sample questions related to it.

**About Complexity Theory**

Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem.

The most common resources

- time (how many steps it takes to solve a problem)
- space (how much memory it takes)

Other resources, e.g.,how many parallel processors are needed to solve a problem in parallel Computability theory deals with whether a problem can be solved at all, regardless of the resources required.

**Problems and instances**

A single problem is an entire set of related questions, where each question is a finite-length string.

The FACTORIZE problem

- given an integer written in binary
- return all of the prime factors of that number

A particular question is called an instance. Instance of the FACTORIZE problem is give the factors of the number 15

**Decision problems**

Much of complexity theory deals with decision problems. A decision problem is a problem where the answer is always yes/no.

The IS-PRIME problem

- given an integer written in binary
- return whether it is a prime number or not

Decision problems are often considered because an arbitrary problem can always be reduced to a decision problem.

**Complexity classes**

The complexity class P is the set of decision problems that can be solved by a deterministic machine in polynomial time. This class corresponds to an intuitive idea of the problems which can be effectively solved in the worst cases. The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time.This class contains many problems that people would like to be able to solve effectively, including the Boolean satisfiability problem, All the problems in this class have the property that their solutions can be checked effectively. The question of whether P is the same set as NP is the most important open question in theoretical computer science.

**Download Questions on AMCAT Complexity Theory **

AMCAT Complexity Theory Practice Question Download

**Practice Questions on Complexity Theory**

Below is a list of AMCAT Complexity Theory Questions to practice and learn:

**Question 1
**In case of the worst timing, which might be the worst to implement in sorting algorithm?

**A. Quick**

**B. Merge**

**C. Tim**

**D. Heap**

**Quick sort has worse time complexity of O(n^2)**

Answer: Option A

Explanation:

Answer: Option A

Explanation:

**Question 2
**In case of the worst timing, which might be the worst to implement in sorting algorithm?

**A. Quick**

**B. Merge**

**C. Tim**

**D. Heap**

**Answer: Option C**

**Explanation:**Quick sort has worse time complexity of O(n^2)

**Question 3
**There are 2 buildings and on each’s window, a flower pot is kept. Ravi’s mother tells him to add each cell/window to the other and store in a matrix? What would be time complexity if he writes a code to do so?

**A. Theta(n)**

**B. Theta( log n)**

**C. Theta(n^2)**

**D. Theta(n log n)**

Answer: Option A

Answer: Option A

**Question 4
**Which of the following has the quickest average time complexity?

**A. Quick**

**B. Radix**

**C. Bubble**

**D. Heap**

**Radix sort is quickest amongst these in average time**

Answer: Option B

Explanation:

Answer: Option B

Explanation:

**Question 5
**In regards to time complexity which will perform better ω(n^4) or O(n^3)?

**A. ω(n^4)**

**B. O(n^3)**

**C. Both Equally**

**D. Cannot be said**

**ω(n^4) as it is omega is measured for best time complexity**

Answer: Option A

Explanation:

Answer: Option A

Explanation:

**Question 6
**Which of the following case does not exist in complexity theory?

**A. Best case**

**B. Worst case**

**C. Average case**

**D. Null case**

**Null case does not exist in complexity Theory.**

Answer: Option D

Explanation:

Answer: Option D

Explanation:

Hope the mock AMCAT Complexity Theory Questions helps in understanding the topic.

Download AMCAT Questions on Polymorphism

AMCAT Sample Questions on Heaps

Mock test questions on Abstraction