Understanding Time complexity calculation for Dijkstra Algorithm

Dijkstra’s shortest path algorithm is O(ElogV) where:

  • V is the number of vertices
  • E is the total number of edges

Your analysis is correct, but your symbols have different meanings! You say the algorithm is O(VElogV) where:

  • V is the number of vertices
  • E is the maximum number of edges attached to a single node.

Let’s rename your E to N. So one analysis says O(ElogV) and another says O(VNlogV). Both are correct and in fact E = O(VN). The difference is that ElogV is a tighter estimation.

Related Posts:

  1. What does O(log n) mean exactly?
  2. What does O(log n) mean exactly?
  3. Breadth First Search time complexity analysis
  4. O(n log n) vs O(n) — practical differences in time complexity
  5. Which is better: O(n log n) or O(n^2)
  6. Difference between Big-O and Little-O Notation
  7. Why is O(n) better than O( nlog(n) )?
  8. A tool for calculating the big-O time complexity of Java code? [closed]
  9. Is Dijkstra’s algorithm for directed or undirected graphs?
  10. How do I check if an array includes a value in JavaScript?
  11. Dijkstra’s algorithm in python
  12. how to calculate binary search complexity
  13. Dijkstra’s algorithm in python
  14. Why is the time complexity of both DFS and BFS O( V + E )
  15. Time complexity of a Priority Queue in C++
  16. Explanation of runtimes of BFS and DFS
  17. Counting the sum of every nodes’ neighbors’ degrees?
  18. Time Complexity of the Kruskal Algorithm?
  19. Difference and advantages between dijkstra & A star
  20. Example of O(n!)?
  21. When will the worst case of Merge Sort occur?
  22. Big O, how do you calculate/approximate it?
  23. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  24. How can I create an array of linked lists in java?
  25. Good Java graph algorithm library?
  26. Best case time complexity for selection sort
  27. Trie complexity and searching
  28. Is log(n!) = Θ(n·log(n))?
  29. Is complexity O(log(n)) equivalent to O(sqrt(n))?
  30. How to calculate big-theta
  31. What is the time complexity of while loops?
  32. Merge sort time and space complexity
  33. Why lookup in a Binary Search Tree is O(log(n))?
  34. How to calculate time complexity of backtracking algorithm?
  35. Hash table runtime complexity (insert, search and delete)
  36. Quickselect time complexity explained
  37. What’s the difference between uniform-cost search and Dijkstra’s algorithm?
  38. Order functions by growth rate
  39. Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
  40. Big Oh for (n log n)
  41. What is the big-O of the function (log n)^k
  42. How do I find the time complexity (Big O) of while loop?
  43. Is there an O(n) integer sorting algorithm?
  44. Computational complexity of Fibonacci Sequence
  45. Which algorithm is faster O(N) or O(2N)?
  46. Difference between Big-Theta and Big O notation in simple language
  47. Time complexity of nested for-loop
  48. How are the following functions O(N^3)?
  49. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  50. Are there any real O(n^n) algorithms?
  51. Running time of algorithm A is at least O(n²) – Why is it meaningless?
  52. In a triangulated isometric grid, what triangle is a given point in?
  53. What is a loop invariant?
  54. When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
  55. what does O(N) mean [duplicate]
  56. matplotlib savefig() plots different from show()
  57. Python: maximum recursion depth exceeded while calling a Python object
  58. A proper way to create a matrix in c++
  59. How do you change the size of figures drawn with Matplotlib?
  60. Time Complexity of Prims Algorithm?
  61. Determining complexity for recursive functions (Big O notation)
  62. Quick Sort Vs Merge Sort
  63. Polynomial time and exponential time
  64. Python equivalent to ‘hold on’ in Matlab
  65. Insertion Sort vs. Selection Sort
  66. How to find the kth smallest element in the union of two sorted arrays?
  67. Find how many connected groups of nodes in a given adjacency matrix
  68. Python: maximum recursion depth exceeded while calling a Python object
  69. longest increasing subsequence(O(nlogn))
  70. When should I use Kruskal as opposed to Prim (and vice versa)?
  71. Trying to understand max heapify
  72. What is the meaning of “exclusive” and “inclusive” when describing number ranges?
  73. Intuition for perceptron weight update rule
  74. Easy: Solve T(n)=T(n-1)+n by Iteration Method
  75. Quicksort vs heapsort
  76. Efficient swapping of elements of an array in Java
  77. Properly formatted multiplication table
  78. Looking for algorithm finding euler path
  79. What is the maximum number of edges in a directed graph with n nodes?
  80. Java, Shifting Elements in an Array
  81. Creating a maze solving algorithm in Java
  82. How to find maximum spanning tree?
  83. Image rotation algorithm
  84. Algorithm to return all combinations of k elements from n
  85. hash function for string
  86. Best way to reverse a string
  87. Calculate distance between two latitude-longitude points? (Haversine formula)
  88. Median of Medians in Java
  89. What is the difference between a heuristic and an algorithm?
  90. Edit Distance in Python
  91. How to calculate an angle from three points?
  92. the asymptotic growth of n choose floor(n/2)
  93. How to implement a most-recently-used cache
  94. What is the time and space complexity of a breadth first and depth first tree traversal?
  95. Finding all possible combinations of numbers to reach a given sum
  96. What is O(log(n!)) and O(n!) and Stirling Approximation
  97. Finding square root without using sqrt function?
  98. How to determine if a point is in a 2D triangle?
  99. Big O Complexity in Binary Search Tree(BST)
  100. About bubble sort vs merge sort

Leave a Comment