## AMCAT COMPUTER PROGRAMMING PREVIOUS QUESTIONS (PAPERS) – 12

Ques54. A code takes the following code steps (equivalently time unit) to execute:

5*n3 + 6*n2 + 1. Which of the following is not true about the time complexity of the

program?

Op 1: It has a time complexity of O(n3

)

Op 2: It has a time complexity of O(n4

)

Op 3: It has a time complexity of O(n2

)

Op 4: It has a time complexity of &theta(n3

)

Op 5:

Correct Op : 3

Ques55. We have two programs. We know that the first has a time complexity O(n2

),

while the second has a complexity &omega(n2

). For sufficiently large n, which of the

following cannot be true?

Op 1: Both codes have same complexity

Op 2: The first code has higher time complexity than the second

Op 3: The second code has lower time complexity than the first code.

Op 4: Both codes are the same.

Op 5:

Correct Op : 2

Ques56. The time complexity of code A is &theta(n), while for Code B it is

&theta(log(n)). Which of the following is true for sufficiently large n?

Op 1: Both code have the same time complexity

Op 2: Code A has higher time complexity

Op 3: Code B has higher time complexity

Op 4: No comparison can be made between the time complexity of the two codes.

Op 5:

Correct Op : 2

Ques57. 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 realizes that the

number of iterations required is more than n. What can she claim with regard to the

complexity of the code?

Op 1: It is O(n)

Op 2: It is O(n2)

Op 3: It is &theta(n)

Op 4: It is &omega(n)

Op 5:

Correct Op : 4

Ques58. Gautam is given two codes, A and B, to solve a problem, which have

complexity &theta(n) and &theta(n2) respectively. His client wants to solve a problem

of size k, which Gautam does not know. Which code will Gautam deliver to the client,

so that the execution is faster?

Op 1: Code A

Op 2: Code B

Op 3: Gautam cannot determine

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

Op 5:

Correct Op : 3

Ques59. Surbhi is given two codes, A and B, to solve a problem, which have complexity

O(n3) and &omega(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?

Op 1: Code A

Op 2: Code B

Op 3: Surbhi cannot determine

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

Op 5:

Correct Op : 1

Ques60. Vibhu is given two codes, A and B, to solve a problem, which have complexity

O(n4) and &omega(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?

Op 1: Code A

Op 2: Code B

Op 3: Vibhu cannot determine

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

Op 5:

Correct Op : 3

Ques61. Pavithra is given two codes, A and B, to solve a problem, which have

complexity &theta(n3) and &omega(n3) respectively. Her client wants to solve a

problem of size k, which is sufficiently large. Which code should she deliver to the

client in the present scenario?

Op 1: Code A

Op 2: Code B

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

Op 4: None of these

Op 5:

Correct Op : 1

Ques61. Code A has to execute 4*n2 + 64 program statements, while Code B has to

execute 32*n program statements for a problem of size n. The time for executing a

single program statement is same for all statements. Rajesh was given a problem

with a certain size k and he delivered Code A. What could be the possible value of k?

Op 1: 1000

Op 2: 5

Op 3: 10

Op 4: 3

Op 5:

Correct Op : 4

Ques63. Saumya writes a code which has a function which calls itself. Which

programming concept is Saumya using?

Op 1: This is bad programming practice and should not be done.

Op 2: Recursion

Op 3: Decision Making

Op 4: Overloading

Op 5:

Correct Op : 2

Ques64. Shrishti writes the code for a function that computes the factorial of the

inputted number n.

function factorial(n)

{

if(n equals 1)

return 1

else

— MISSING STATEMENT —

end

}

Fill in the missing statement.

Op 1: return factorial(n-1)

Op 2: return n*factorial(n)

Op 3: return n*(n-1)

Op 4: return n*factorial(n-1)

Op 5:

Correct Op : 4