Algorithms: Design and Analysis, Part 1 - Exam Question 5

Problem:

What is the running time of depth - first search, as a function of n and m, if the input graph $G = (V,E)$ is represented by an adjacency matrix (i.e., NOT an adjacency list), where as usual $n=|V|$ and $m=|E|$ ?

Solution:

Each node need to be gone through. And for each of them it need to look at all other nodes for a possible edge, so the time is $\theta(n^2)$.