Can you optimize the Kruskal algorithm for a complete graph, which runs in O(E+V) logV to O(VlogV), where E is the number of edges and V is the number of vertices in the graph?
You need to look at every edge, so there is no way to beat [math]\Omega(E)[\math] time. In particular, for a complete graph, [math]V\log V[\math] is [math]o(E)[\math], so this is impossible.There do exist algorithms that find the minimal spanning tree in time [math]O(E + V\log V)[\math], though (in particular, Prim's algorithm implemented with a Fibonacci heap; see Prim's algorithm. ) I believe it is open whether there exists an algorithm for minimal spanning tree that runs in [math]O(E)[\math] time (interestingly though, the optimal algorithm is known; we just don't know how to analyze its running time; see Minimum spanning tree).
What is the difference in Kruskal's and Prim's algorithm?
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges.In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees of the same graph.The two most popular algorithms for minimum spanning tree are :Kruskal’s Algorithm : Kruskal's algorithm can be shown to run in O(E log E) time, or equivalently, O(E log V) time, where E is the number of edges in the graph and V is the number of vertices, all with simple data structures.Prim’s Algoritm : The time complexity is O(VlogV + ElogV) = O(ElogV), making it the same as Kruskal's algorithm. However, Prim's algorithm can be improved using Fibonacci Heaps to O(E + logV).Kruskal’s Algorithm : performs better in typical situations (sparse graphs) because it uses simpler data structures.Prim's Algorithm : is significantly faster in the limit when you've got a really dense graph with many more edges than vertices.Use Prim's algorithm when you have a graph with lots of edges else use Kruskal’s algorithm.Following illustration is the procedure for the respective algorithms :Implementation :Kruskal’s Algorithm : Kruskal’s Algorithm in C [Program & Algorithm] - The Crazy ProgrammerPrim’s Algorithm : Prim's Algorithm in C [Program & Algorithm] - The Crazy Programmer
What is the worst case time complexity of a bottom-up heap sort?
It is O(n). Check out the video for the explanation.Here is SO link as well - How can building a heap be O(n) time complexity? , check out the second ans.
How do I analyze time complexity of prims MST algorithm?
To analyze the Time Complexity of Prim's algorithm, I have used a Binary Heap in this case.MST-PRIM(G, w, r)for each u ∈ G.V u.key ← ∞ u.π ← NIL r.key ← 0 Q ← G.V while Q ≠ Ø u ← EXTRACT-MIN(Q) for each v ∈ G.Adj[u] if v ∈ Q and w(u, v) < v.key v.π ← u v.key ← w(u, v)Here you can see that, time required for one call to EXTRACT-MIN(Q) = O(log V) [using min priority queue]. The while loop at line 6 is executing total V times. So EXTRACT-MIN(Q) is called V times. So total time required for EXTRACT-MIN(Q) = O(VlogV).the for loop at line 8 is executing total 2E times ( as total length of all the adjacency lists=2E for undirected graph ) . Time required for executing line 11=O(log v) [using DECREASE_KEY operation on the min heap]. Line 11 is executing total 2E times. So total time required to execute line 11=O(2Elog V) = O(Elog v).The for loop at line 1 will be executed for V times. Using BUILD_HEAP procedure, to perform lines 1 to 5, it will require O(V) timesTotal time complexity of MST-PRIM = time required for executing 1 + time required for executing 2 + time required for executing 3 =Total : O( VlogV + ElogV + V) = O(ElogV)Hope this explains what you need to know.Keep coding !! :)
Why does some algorithm has the same output?
As Harris Siddiqui commented, “deterministic algorithm”. Keeping things simple.The definition of the word can be stated as:a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer.Broadly speaking:a process or a set of rules to be followed to do something.Lets take a break an make some tea.Algorithm #1:Pour measured amount of water in a pot.Place it on the stove.Turn the stove on.Wait till water comes to boil.Add Tea leaves (1 tea spoon per cup)Turn stove offCover pot.Steep for five minutes.Pour in cup through sieve.Sip carefully and enjoy. Warning contents might be hot!or maybe;Algorithm #2:Pour measured amount of water in an electric kettle.Turn it on.Wait for water to boil.Place tea bag in cup.Pour hot water in cup.Dip tea bag till desired concentration.Sip carefully and enjoy. Warning contents might be hot!Essentially, both algorithms give you the same end result. Just different ways of doing the same thing.Now to specifically answer your question in short form:Why do different algorithms produce the same output?Because, they are designed to do that.