Databases
StackOverflow2013
Postsdbo
POAlgorithm Perfection Vs Time Analysis : Does Time complexity matters everytime?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm Perfection Vs Time Analysis : Does Time complexity matters everytime?
    primarykey
    data
    text
    <p>I have a very basic and general doubt related to algorithm design. I've learnt basic algorithm and now learning randomized algorithm. Everywhere I observed that a professor mostly focuses on designing the algorithm that will ultimately try to reduces the complexity. </p> <p>The usual way(What I observed) is to learn some basic(or an older) algorithm which behaves badly in terms of complexity and so the objective is to modify that older one with a newer algorithm which should focus on reducing the complexity, without affecting the output. </p> <p>But in most of algorithm I've studied, especially distributed algorithms (in distributed operating systems) such as algorithms for distributed mutual exclusion, distributed deadlock detection etc., what I observed is that(and mostly I think that) the design of the algorithm should not focus only on complexity enhancement but it should focus on the perfection of the algorithm as well. </p> <p>Lets take an example of distributed mutual exclusion algorithm. The very basic algorithm is a Lamport's algorithm and the modified version(by enhancing the complexity) of it is the Ricart-Agarwala algorithm. Since in distributed environment the communication is mostly by means of message passing, for distributed mutual exclusion we have three kinds of messages : a) Request critical resource b) Reply the request c) Release critical resource. The basic algorithm uses extra release messages(to inform all sites that the my site has released the critical resource, so you can enter). But in the advanced version what they did is they discarded these release messages by accommodating it in reply messages. And so they came up with some reduced complexity solution. </p> <p>But when I tried the implementation of these algorithms in java, I observed that even if the complexity of basic algorithm was bit higher but it was more perfect than the advanced one. Because by reducing the number of messages transferred (in advanced solution), local site is no longer aware of the fact that remote site has actually released the resource or not because on the confirmation of release message only site updates its local data structures such as request queue etc. If we don't send any explicit notification for release, then requests remains pending unnecessarily in request queue of the local site for entire run.</p> <p><code>So my doubt is that if enhancement of complexity is so important, why can't perfection ? I mean if algorithm is producing perfect results at the cost of bit higher complexity then how does it matters as far as I am getting perfection in output as compared to the enhanced complexity solution which lacks in perfection ?</code></p> <p>Note : By perfection I don't mean correct/incorrect results. Results are always correct. Only the perfection or accuracy of the produced result varies.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USWinn
    1. USWinn
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. COIf by "lack of perfection" you mean that you are getting incorrect results, then you should probably assume that you just implemented the algorithm incorrectly.
      singulars
      1. POAlgorithm Perfection Vs Time Analysis : Does Time complexity matters everytime?
      1. USmbeckish
    2. COThe domain of approximation algorithms is exactly about the tradeoff between complexity reduction and result accuracy (if that's indeed what you mean by perfection). If an algorithm is proven to be within a certain distance from the correct answer, it may be good enough for certain practical uses requiring efficient complexity.
      singulars
      1. POAlgorithm Perfection Vs Time Analysis : Does Time complexity matters everytime?
      1. USLeeor
    3. CO@ mbeckish By lack of perfection I don't mean incorrect results. It simply means that the accuracy of results may get reduced if we only focus on the enhancement of complexity. I am not saying that enhancement always reduces perfection, but in certain algorithm like the one I discussed above, accuracy or perfection really matters a lot than complexity enhancement.
      singulars
      1. POAlgorithm Perfection Vs Time Analysis : Does Time complexity matters everytime?
      1. USWinn
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload