Take the 2-minute tour ×

Stupid question I know, but if there is a log is it linear?

share|improve this question

closed as off topic by DCoder, alfasin, martin clayton, j0k, amon Sep 16 '12 at 8:24


In terms of which variable? It is linear in E, and n log n in V. –  David Robinson Sep 16 '12 at 1:21
No, that is linearithmic w.r.t. V (the number of vertices), linear w.r.t. E (the number of edges). This makes sense if you analyze the actual mechanics of the algorithm. –  oldrinb Sep 16 '12 at 1:57
add comment

2 Answers

No, O(VlogV) =/= O(V) because the ratio of VlogV to V diverges to infinity

share|improve this answer
add comment

The answer to the question "if there is a log is it linear" is no. Linear usually refers to O(N)

What this means is that it's dependent on the graph, and that the complexity can be measured more precisely by taking into account both the edges and the vertices. A simpler bound would be O(V^2) because in the worst case |E| = O(V^2) thus O(|V^2| + |V| log |V|) = O(V^2). In the best case |E| = 0, so O(|V| log |V|), so the run time is never really linear.

share|improve this answer
ahh ok. Are there any shortest path algorithms that are linear time? –  Takkun Sep 16 '12 at 1:26
I don't think so - there may be for special classes of graphs, but for a one-algorithm-fits-all-graphs there is none. –  dfb Sep 16 '12 at 1:34
add comment
