I am trying to figure out an overall
O(...) expression given
F for a word ladder or word chain that I have written in
Java and it works. I am using
undirected graph with
What is known, and I have calculated.
O(V + E) for building the graph
G(V, E) of words. And the second time complexity is in a while and for loop of finding the shortest path (or using BFS) which is
O(V^2) a time complexity being quadratic.
O(v) from a “worst case scenario”. The Graph holds all the words, and number of vertices (or nodes) and number of edges. The Nodes are made up of a single Node class object which contains
- Program loads into buffer a file with words.
- The program builds the graph.
- The program runs test and loads into buffer information from a test file (different file). Then selects start, and end node and performs the shortest path search.
Now, I am trying to come up with an
O(n) time complexity or total time cost/performance for
V = number of vertices
E = number of edges
F = number of test cases, one for each line in the test file
What I am essentially trying to express is: O(…) something, for V, E, F but not separately but a total, given size of Graph(V, E) and size of input testfile.