Register

NIELIT 2017 July Scientist B (CS) - Section B: 42

• retagged by
2,365 views
0 0 votes

Let $G$ be a graph with $n$ vertices and $m$ edges.What is the tightest upper bound on the running time of Depth First Search of $G$, when $G$ is represented using adjacency matrix?

  1. $O(n)$
  2. $O(m+n)$
  3. $O(n^2)$
  4. $O(mn)$

2 Answers

1 1 vote
Option C

Let G be a graph with n vertices and m edges. the tightest upper bound on the running time of Depth First Search of G,

when G is represented as an adjacency matrix=$O(n^{2})$

when G is represented as an adjacency list=$O(n+m)$
Voting & Accepting an answer helps improve the community
Answer:
← Previous · NIELIT 2017 July Sci...Next → · NIELIT 2017 July Sci...
← Previous in category · NIELIT 2017 July Sci...Next in category → · NIELIT 2017 July Sci...
Position:
Show:

Related questions

2 2 votes
1 1 answer
1.3k
1.3k views
admin asked Mar 30, 2020
1,251 views
NIELIT 2017 July Scientist B (CS) - Section B: 9
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are$\Theta(n \log n),\Theta(n \log n) \text{ and } \Theta(n^2)$$\Theta(n^2),\Thet...
0 0 votes
3 3 answers
7.2k
7.2k views
admin asked Mar 30, 2020
7,197 views
NIELIT 2017 July Scientist B (CS) - Section B: 39
Which of the following standard algorithms is not Dynamic Programming based?Bellman-Ford Algorithm for single source shortest pathFloyd Warshall Algorithm for all pairs s...
0 0 votes
1 1 answer
1.4k
1.4k views
admin asked Mar 30, 2020
1,393 views
NIELIT 2017 July Scientist B (CS) - Section B: 41
Four Matrices $M_1, M_2, M_3$ and $M_4$ of dimensions $ p \times q$, $q \times r$, $r \times s$ and $s \times t$ respectively can be multiplied in several ways with diffe...
1 1 vote
1 1 answer
1.4k
1.4k views
admin asked Mar 30, 2020
1,386 views
NIELIT 2017 July Scientist B (CS) - Section B: 55
Suppose $T(n)=2T(n/2)+n$, $T(0)=T(1)=1$ which one of the following is false?$T(n)=O(n^2)$$T(n)=\Theta(n\log n)$$T(n)=\Omega(n^2)$$T(n)=O(n\log n)$