1. In analysis of algorithm, approximate relationship between the size of the job and
the amount of work required to do is expressed by using _________

Central tendency

Differential equation

Order of execution

Order of magnitude

Order of Storage

Order of execution

2. Worst case efficiency of binary search is

log2 n + 1

n

2n

log n.

log2 n + 1

3. For defining the best time complexity, let f (n) = log n and g (n) = √n, _________

f (n) Ω(g(n)), but g(n) Ω (f(n))

f (n) Ω(g(n)), but g(n) Ω (f(n))

f (n) Ω(g(n)), and g(n) Ω (f(n))

f (n) Ω(g(n)), and g(n) Ω (f(n))

f (n) Ω(g(n)), but g(n) Ω (f(n))

4. For analyzing an algorithm, which is better computing time?

O (100 Log N)

O (N) (c)O (2N)

O (N logN)

O (N2).

O (100 Log N)

5. Let f, t: N→R 0, and t (n) O (f (n)) iff t(n)≤ c.f (n) where cis positive real
constant andn≥ no, then no is ___________

Upper bound

Lower bound

Duality value

Threshold value

Maximum value.

Lower bound

6. Consider the usual algorithm for determining whether a sequence of parentheses is
balanced. What is the maximum number of parentheses that will appear on the stack
AT ANY ONE TIME when the algorithm analyzes: (()(())(()))

1

2

3

4

3

7. Breadth first search __________

Scans each incident node along with its children.

Scans all incident edges before moving to other node.

Issame as backtracking

Scans all the nodes in random order.

Scans all incident edges before moving to other node.

8. Which method of traversal does not use stack to hold nodes that are waiting to be
processed?

Dept First

D-search

Breadth first

Back-tracking

Breadth first

9. The Knapsack problem where the objective function is to minimize the profit is
______

Greedy

Dynamic 0 / 1

Back tracking

Branch & Bound 0/1

Branch & Bound 0/1

10. Choose the correct answer for the following statements: I. The theory of NP–completeness provides a method of obtaining a
polynomial time for NPalgorithms.
II. All NP-complete problem are NP-Hard.