## 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 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