2 Replies Latest reply: Dec 15, 2009 8:36 AM by 843853 RSS

    General Algorithm Question

    843853
      This is a general programming algorithm question opposed to specifc java based but i hope you can help

      How can we say Prims algorithm is betetr than Kruskal or visa versa when their time complexitys are different

      O(n log n) - Kruskal
      O(n^2) - Prim

      I appreciate it has something to do with whether the graph is sparse or dence but cant find any resources to aid me in understanding this

      So far my understanding is that a dence graph is best suited to Prim as it sequentially finds the next route based on
      1) node being unused
      2)less weight than any other path

      However with Kruskel its a greedy algorithm, essentially adding all weights and connections to a heap <? not sure about that> and selecting each cheapest path until all nodes are used. It has no view to the bigger picture wich makes it a little naieve and thus better for sparse graphs

      so basically back to the question, how can the 2 be compared for situations where 1 is betetr than the other or where there is a case that the 2 may not differ tooo much from each other

      thanks
        • 1. Re: General Algorithm Question
          843853
          compSciUndergrad wrote:
          This is a general programming algorithm question opposed to specifc java based but i hope you can help
          There's a specific forum for general algorithm questions. So it's OK that you asked it, but here's not the place.
          so basically back to the question, how can the 2 be compared for situations where 1 is betetr than the other or where there is a case that the 2 may not differ tooo much from each other
          It sounds like you just did. Are you being asked for something more qualitative? You can start by identifying the worst and best case complexities for each algorithm, and when they occur (for example, Quicksort is on average O(n log n) but has a worst-case complexity of O(n^2) which can be encountered if you don't randomize the pivots and the list is already sorted).

          Perhaps what you need to do is prove it inductively? As in, for all graphs of N nodes and K or more edges, Prim's is better. But it seems like such a proof would require such a precise set of circumstances that it would be hard to generalize into an inductive proof.
          • 2. This Thread is now moved
            843853
            Note: This thread was originally posted in the [New To Java|http://forums.sun.com/forum.jspa?forumID=54] forum, but moved to this forum for closer topic alignment.