Big O Notation of Algorithm composed of smaller algorithms

Question

I am working on an assignment which takes some a graph, adds an extra vertex to the graph, applies Bellman Ford with the new vertex as the source, then uses applies Dijkstra's all pairs to the graph.

The algorithms being used have run-times/space requirements of:

Adding extra vertex
-- Running Time: V
-- Space: V
Bellman Ford single source shortest path algorithm
-- Running time: EV
-- Space: V
Dijkstra's all pairs shortest path algorithm
-- Running time: EV log V
-- Space: V

I am having difficulty understanding if I am calculating the big O of the total process. Each program is run separately, and the output is piped from program to program. My though is the total algorithm would have a Big-O run time of:

O( V + EV + EV log V ) which would simplify to O( EV log V )

The space requirement would be calculated in a similar fashion. I'm I thinking of this correctly? Thanks!

Answer 1

Exactly, a "rule of thumb" is that, in a sequence of code blocks, the overall complexity is dominated by the block with greatest complexity (asymptotically)

Matematically, when V tends to very large numbers, it's smaller than EV, which is smaller than EVlogV. So, for large V, the complexity of your algorithm is approximated well by EVlogV