Dijkstra’s shortest path algorithm is O(ElogV)
where:
V
is the number of verticesE
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 verticesE
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:
- What does O(log n) mean exactly?
- What does O(log n) mean exactly?
- Breadth First Search time complexity analysis
- O(n log n) vs O(n) — practical differences in time complexity
- Which is better: O(n log n) or O(n^2)
- Difference between Big-O and Little-O Notation
- Why is O(n) better than O( nlog(n) )?
- A tool for calculating the big-O time complexity of Java code? [closed]
- Is Dijkstra’s algorithm for directed or undirected graphs?
- How do I check if an array includes a value in JavaScript?
- Dijkstra’s algorithm in python
- how to calculate binary search complexity
- Dijkstra’s algorithm in python
- Why is the time complexity of both DFS and BFS O( V + E )
- Time complexity of a Priority Queue in C++
- Explanation of runtimes of BFS and DFS
- Counting the sum of every nodes’ neighbors’ degrees?
- Time Complexity of the Kruskal Algorithm?
- Difference and advantages between dijkstra & A star
- Example of O(n!)?
- When will the worst case of Merge Sort occur?
- Big O, how do you calculate/approximate it?
- Why doesn’t Dijkstra’s algorithm work for negative weight edges?
- How can I create an array of linked lists in java?
- Good Java graph algorithm library?
- Best case time complexity for selection sort
- Trie complexity and searching
- Is log(n!) = Θ(n·log(n))?
- Is complexity O(log(n)) equivalent to O(sqrt(n))?
- How to calculate big-theta
- What is the time complexity of while loops?
- Merge sort time and space complexity
- Why lookup in a Binary Search Tree is O(log(n))?
- How to calculate time complexity of backtracking algorithm?
- Hash table runtime complexity (insert, search and delete)
- Quickselect time complexity explained
- What’s the difference between uniform-cost search and Dijkstra’s algorithm?
- Order functions by growth rate
- Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
- Big Oh for (n log n)
- What is the big-O of the function (log n)^k
- How do I find the time complexity (Big O) of while loop?
- Is there an O(n) integer sorting algorithm?
- Computational complexity of Fibonacci Sequence
- Which algorithm is faster O(N) or O(2N)?
- Difference between Big-Theta and Big O notation in simple language
- Time complexity of nested for-loop
- How are the following functions O(N^3)?
- Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
- Are there any real O(n^n) algorithms?
- Running time of algorithm A is at least O(n²) – Why is it meaningless?
- In a triangulated isometric grid, what triangle is a given point in?
- What is a loop invariant?
- When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]
- what does O(N) mean [duplicate]
- matplotlib savefig() plots different from show()
- Python: maximum recursion depth exceeded while calling a Python object
- A proper way to create a matrix in c++
- How do you change the size of figures drawn with Matplotlib?
- Time Complexity of Prims Algorithm?
- Determining complexity for recursive functions (Big O notation)
- Quick Sort Vs Merge Sort
- Polynomial time and exponential time
- Python equivalent to ‘hold on’ in Matlab
- Insertion Sort vs. Selection Sort
- How to find the kth smallest element in the union of two sorted arrays?
- Find how many connected groups of nodes in a given adjacency matrix
- Python: maximum recursion depth exceeded while calling a Python object
- longest increasing subsequence(O(nlogn))
- When should I use Kruskal as opposed to Prim (and vice versa)?
- Trying to understand max heapify
- What is the meaning of “exclusive” and “inclusive” when describing number ranges?
- Intuition for perceptron weight update rule
- Easy: Solve T(n)=T(n-1)+n by Iteration Method
- Quicksort vs heapsort
- Efficient swapping of elements of an array in Java
- Properly formatted multiplication table
- Looking for algorithm finding euler path
- What is the maximum number of edges in a directed graph with n nodes?
- Java, Shifting Elements in an Array
- Creating a maze solving algorithm in Java
- How to find maximum spanning tree?
- Image rotation algorithm
- Algorithm to return all combinations of k elements from n
- hash function for string
- Best way to reverse a string
- Calculate distance between two latitude-longitude points? (Haversine formula)
- Median of Medians in Java
- What is the difference between a heuristic and an algorithm?
- Edit Distance in Python
- How to calculate an angle from three points?
- the asymptotic growth of n choose floor(n/2)
- How to implement a most-recently-used cache
- What is the time and space complexity of a breadth first and depth first tree traversal?
- Finding all possible combinations of numbers to reach a given sum
- What is O(log(n!)) and O(n!) and Stirling Approximation
- Finding square root without using sqrt function?
- How to determine if a point is in a 2D triangle?
- Big O Complexity in Binary Search Tree(BST)
- About bubble sort vs merge sort