Scribd
Upload
160 views3 pages

AMCAT Complexity Theory Questions

The document contains 10 questions about complexity theory from an AMCAT exam. The questions cover topics like time complexity of sorting algorithms like quicksort and mergesort, space complexity, best/worst/average cases. For example, one question asks about the time complexity of adding elements of two matrices of size n and the answer is Theta(n) since it would involve n additions. Another asks about the worst case time complexity of linear search and the answer is O(n) when the item is not present in the array.

Uploaded by

Shilpi Malaiya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
160 views3 pages

AMCAT Complexity Theory Questions

The document contains 10 questions about complexity theory from an AMCAT exam. The questions cover topics like time complexity of sorting algorithms like quicksort and mergesort, space complexity, best/worst/average cases. For example, one question asks about the time complexity of adding elements of two matrices of size n and the answer is Theta(n) since it would involve n additions. Another asks about the worst case time complexity of linear search and the answer is O(n) when the item is not present in the array.

Uploaded by

Shilpi Malaiya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

AMCAT Complexity Theory Questions

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
Answer: Option A
Explanation: Quick sort has worse time complexity of O(n^2)

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

Question 4
Which of the following has the quickest average time complexity?
A. Quick
B. Radix
C. Bubble
D. Heap
Answer: Option B
Explanation: Radix sort is quickest amongst these in average time
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
Answer: Option A
Explanation: ω(n^4) as it is omega is measured for best time complexity

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
Answer: Option D
Explanation: Null case does not exist in complexity Theory.

Question 7
The complexity of linear search algorithm is
A. O(n)
B. O(log n)
C. O(n2)
D. O(n log n)
Answer: Option A
Explanation: The worst case complexity of linear search is O(n).

Question 8
The Worst case occur in linear search algorithm when
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or is not there at all
Answer: Option D
Explanation: The Worst case occur in linear search algorithm when Item is the last element in
the array or is not there at all.

Question 9
What is space complexity of the program?
A. Amount of hard disk space required to store the program.
B. Amount of hard disk space required to compile the program.
C. Amount of memory required by the program to run.
D. Amount of memory required by the program to compile.
Answer: Option C

Question 10
A code with θ(n) and θ(n^2). Which code will execute faster for a code of size J?
A. θ(n)
B. θ(n2)
C. Cannot be said as size of K is unknown
D. Both will be equal
Answer: Option C

You might also like