Depth-First Search runtime measuring
<p>I'm currently studying the Depth-First Search algorithm and although i've confirmed that it does run in O(N+M) it still doesn't show up very well when i measure runtime, since in a graph with 2000 to 16000 nodes, and a constant 50000 edges. The runtime remains almost constant (close to 0,5 seconds), as if the nodes aren't doing much on it. Is there a way to get a more significant change in the runtime without adding too many more nodes?</p>

<p>I'm using an implementation in Python and using the command "time" to measure the runtime.</p>

<p>The problem may be that Python has relatively high overhead (reading and analyzing the program). Check out this question: <a href="http://stackoverflow.com/questions/582336/how-can-you-profile-a-python-script">How can you profile a Python script?</a>.</p>

<p>More specifically, </p>

<pre><code>python -m cProfile myscript.py
</code></pre>

<p>should show you the total time (<code>tottime</code>) spent on the function that actually does the DFS.</p>

python algorithm time-complexity