7. (5 Points) Given the two implementation of ConnectedComponent interface Conne

Question

7. (5 Points) Given the two implementation of ConnectedComponent interface ConnectedComponent_GraphImpl and ConnectedComponent_UFImpl (source code provided in the zip file), one uses Graph class and one uses weighted union-find, compare their worst-case running time and provide the results in the following table. Assuming there are V vertices and E edges.

7.(5 Points) Given the two implementation of ConnectedComponent interface ConnectedComponent_Graphlmpl and ConnectedComponent_UFImpl (source code provided in the zip file), one uses Graph class and one uses weighted union-find, compare their worst-case running time and provide the results in the following table. Assuming there are V vertices and E edges. Graph Implementation Weighted QF Implementation Total running time for adding E edges (joining E pairs) connected getComponentld getComponentCount

Explanation / Answer

Hi.

Today, let me tell you a very generic method to solve any such type of questions.

Let's take the example of any method let's say, getComponentId(). For any such problem our first step should be to analyze the worst case. In this case, for example, we are passing a number say v and finding out the component id where v belongs to using "public int getComponentId(int v)" , so the worst case scenario, ofcourse would be when the number for which we are searching id should recite at the last element or component id while traversing.

More deeply, like if we are using DFS(Depth first search) the node for which we are searching should recite at the last position so that the time taken will be more than any other node while searching, or even more worse case can be not finding the element for which we are searching in the list/graph/QF. Here, the program will search the entire list including last node/vertex/element, but is still not able to find the desired result. So, it will take more time.

Once, we are done figuring out the worst cases, our next step is to call that method expecting worst case and find the time taken by it. This can be done using the difference between the start time and stop time or end time of calling the method for worst case.

You will get a more clear idea by looking at this psuedo code:-

Start Time = Time just before calling method for worst case

call method for worst case

End Time = Time just after end of execution for worst case

Time Difference = End Time - Start Time

You will get a fair idea by having a look at this code:-

long startTime = System.nanoTime(); getComponentId(v); //where v is any integer not in list long endTime = System.nanoTime(); long totalTime = endTime - startTime;

System.out.println(totalTime);

Hope, now you are clear with this concept and can solve any such problem related to worst case, best case or run Time.

Good Luck!!!!

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.