practical vs. theoretical running time

[lewen]

Hello,

I was given an assignment by my teacher to implement some algorithm and analyze its practical running time versus theoretical.

With algorithms running in O(n^2) it's seems to be rather simple. Get execution times for different inputs. Plot on a graph and check if the plotted function behaves anything like n^2.
But what if the running time is defined by multiple variable function, e.g O(V*E) in many graph algorithms.
How should I approach this?
It's possible to plot two different graphs of O(V*E). one assuming that E is constant, second assuming that V is constant. But that won't compare the practical time of O(V*E), or will it?

Thanks in advance.

[Zachm]

For graphs, you can reduce the run-time complexity upper bound from 2 variables dependancy to 1 variable dependancy if you remember that:
1. |V| <= |E|
2. |E| <= |V|^2

From the 2 statements above you can easily deduce the following:
1. f(V,E) = O(|V|*|E|) --> f(V,E) = O(|E|^2)
1. f(V,E) = O(|V|*|E|) --> f(V,E) = O(|V|^3)

where f(V,E) represents the run-time complexity in dependence with V and E. So you can use which ever notations suits your needs best.

Regards,
Zachm

[lewen]

Thanks Zachm,

Your reply also shed light on some other moments I wasn't understanding well in the 'Introduction to algorithms' book.

[ltcmelo]

Hi.

In addition to what Zach has said, there's also an alternative way of analyzing bounds in graph algorithms using the "size" (total number of elements -> vertices + edges) of the graph. For instance, a DFS (depth-first search) on a graph represented by an adjacency list can be said to be linear on the size of the graph, because its complexity is O(V + E) - Note that for a sparse graph this turns into O(V + V) = O(V) and for a dense graph this turns into O(V + V^2) = O(V^2).

Note that I mentioned an adjacency list because when analyzing graph algorithms you might wanna take into consideration how the graph is represented (adjacency list, adjacency matrix, edge list, etc). The same DFS on a graph represented by an adjacency matrix is always O(V ^2).

A last observation I can think of right now is that if you have knowledge about properties of the graph you can always use this information. For example, if a graph is planar, by Euller's formula, the number of edges is directly proportional to the number of vertices. Therefore O(E) = O(V).


Leandro T. C. Melo
GTAD (Graph Toolkit for Algorithms and Drawings) (http://gtad.sourceforge.net/)