Cognizant Complexity Theory Quiz

June 23, 2019

Question 1

Time: 00:00:00
If x1(n) is O(y1(n)) and x2(n) is O(y2(n)), then which of the following options is true in context of asymptotic complexity notations?

x1(n) + x2(n) is O(min(y1(n), y2(n)))

x1(n) + x2(n) is O(min(y1(n), y2(n)))

x1(n) + x2(n) is O(max(y1(n), y2(n)))

x1(n) + x2(n) is O(max(y1(n), y2(n)))

x1(n) + x2(n) is O(y1(n)*y2(n))

x1(n) + x2(n) is O(y1(n)*y2(n))

x1(n) + x2(n) is O(y1(n)-y2(n))

x1(n) + x2(n) is O(y1(n)-y2(n))

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 2

Time: 00:00:00
What is space complexity of the program?

Amount of hard disk space required to store the program.

Amount of hard disk space required to store the program.

Amount of hard disk space required to compile the program.

Amount of hard disk space required to compile the program.

Amount of memory required by the program to run.

Amount of memory required by the program to run.

Amount of memory required by the program to compile.

Amount of memory required by the program to compile.

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 3

Time: 00:00:00
The time required to insert an element in a stack with linked list implementation is?

O(1)

O(1)

O(log2n)

O(log2n)

O(n)

O(n)

O(nlog2n)

O(nlog2n)

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 4

Time: 00:00:00
Choose the correct answer
A Programmer writes an efficient program to sum two square diagonal matrices (matrices with elements only on diagonal). The size of each matrix is nXn. What is the time complexity of Vrinda's algorithm?

Theta (n^2)

Theta (n^2)

Theta (n)

Theta (n)

Theta (n*log(n))

Theta (n*log(n))

None of these

None of these

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 5

Time: 00:00:00
Rajesh implements queue as a singly-linked linked list. The queue has n elements. The time complexity to ADD a new element to the queue:

O (1)

O (1)

O (log2 n)

O (log2 n)

O (n)

O (n)

O (n log2 n)

O (n log2 n)

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 6

Time: 00:00:00
Choose the correct answer
Vibhu is given two codes, A and B, to solve a problem, which have complexity O(n4) and ?(n3) respectively. Her client wants to solve a problem of size k, which is sufficiently large. Which code will Gautam deliver to the client, so that the execution is faster?

Code A

Code A

Code B

Code B

Vibhu cannot determine

Vibhu cannot determine

Both codes have the same execution time, so deliver any.

Both codes have the same execution time, so deliver any.

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 7

Time: 00:00:00
A tree has 5 levels and each has either 4 children or no children. All nodes on the same level have the same number of children. How many nodes are there in the tree? (Root is Level 1)

341

341

256

256

1024

1024

None of these

None of these

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 8

Time: 00:00:00
Surbhi is given two codes, A and B, to solve a problem, which have complexity O(n3) and ?(n4) respectively. Her client wants to solve a problem of size k, which is sufficiently large. Which code will Surbhi deliver to the client, so that the execution is faster?

Code A

Code A

Code B

Code B

Surbhi cannot determine

Surbhi cannot determine

Both codes have the same execution time, so deliver any.

Both codes have the same execution time, so deliver any.

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

Question 9

Time: 00:00:00
Rajini is given an efficient code for summing two nXn matrices and putting the result in a third matrix. She is asked to find it's time complexity. She realises that the number of iterations required is more than n. What can she claim with regard to the complexity of the code?

It is O(n)

It is O(n)

It is O(n2)

It is O(n2)

It is Theta(n)

It is Theta(n)

It is Theta(n2)

It is Theta(n2)

Good Job!

Oops!

  • PrepInsta Explanation
  • User Explanation
Once you attempt the question then PrepInsta explanation will be displayed.

Please login to submit your explanation

Start

["0","40","60","80","100"]
["Need more practice! \r\n \r\n \r\n","Keep trying! \r\n \r\n \r\n","Not bad! \r\n \r\n \r\n","Good work! \r\n \r\n \r\n","Perfect! \r\n \r\n \r\n"]
×

Please login to report