AMDOCS Complexity Theory Problems with Solutions Quiz-1

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(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))

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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 compile the program.

Amount of memory required by the program to run.

Amount of memory required by the program to compile.

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

Question 3

Time: 00:00:00

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

O(1)

O(log2n)

O(n)

O(nlog2n)

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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?

O (1)

O (log2 n)

O (n)

O (n log2 n)

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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:

Code A

Code B

Vibhu cannot determine

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

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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?

341

256

1024

None of these

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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)

Code A

Code B

Surbhi cannot determine

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

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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?

It is O(n)

It is O(n2)

It is Theta(n)

It is Theta(n2)

Good Job!

Oops!

Report the answer

PrepInsta Explanation
User Explanation

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

Please login to submit your explanation

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?

Theta (n^2)

Theta (n)

Theta (n*log(n))

None of these

Good Job!

Oops!