ALGORITHMS |Gate-2012| Previous Year Questions| Set-9

previous year question of ALGORITHMS gate 1993

ALGORITHMS |Gate-2012|

  1. Assuming P ≠ NP, which of the following is TRUE? [GATE – 2012]

a. NP-complete = NP
b. NP-complete ∩ P = ∅
c. NP-hard = NP
d. P = NP-complete

Answer : b)

  1. Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n.  Which of the following is ALWAYS TRUE? [GATE – 2012]

a. A(n) = Ω (W(n))
b. A(n) = Θ (W(n))
c. A(n) = O (W(n))
d. A(n) = o (W(n))

Answer : c)
ALGORITHMS |Gate-2012|


Spread the love

Leave a Comment

Your email address will not be published. Required fields are marked *