Algorithms Design :)

Posted on 2004-11-29
Last Modified: 2010-08-05
How can we modify almost any algorithm to have a good best-case running time?
Question by:adrian_ang
    LVL 3

    Accepted Solution

    Uhh...  "Best-case" running time would be with a dataset of the size of 0, in which case the running time would be constant.  So you wouldn't have to.

    Typically, algorithm analysis is performed for average- or worst- case.  The best-case situation for *any* algorithm is when it doesn't have any data on which to be run.

    Did you mean "worst-case" running time?  I'm not trying to be flip here, but I'm making sure I understand the question...

    LVL 5

    Author Comment

    I mean best - case!
    LVL 5

    Author Comment

    There is always input , for example n integers, if we measure in number of items.
    LVL 23

    Expert Comment


    as baboo mentioned, the best case running time is always going to be a constant.  If you prefer to use big-O notation, then best case scenarios will always be 1-O

    Case in point:

      Suppose we are looking at sorting algorithms.  The Bubble sort is the most basic and has the absolute worst "worst case" scenario.  Conversly, the bubble sort also has the best performance if all of the items are already in order.

    Quick sort (the most common advanced algorithm), overall has one of the best "worst-case" scenarios and a best case (already sorted) that comes very close to that the bubble sort.  

    Finally there is the shear-sort.  For very large datasets that are radically out of sync, this is the absolute best sorting method.  But as it turns out, the efficiency does not change much at all if the data is already pre-sorted.  This makes the "best-case" rather weak.

    In summary, I believe what you are looking for is really minimizing the "worst case" algorithms.  Doing an analysis in this direction will always give you some kind of results.  Only optimizing for best-case will not yield accurate quatitative results.
    LVL 23

    Expert Comment


    I suggest you like into Big O (Big-oh) notation.   I think you'll have more success with what you are looking for

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    How to run any project with ease

    Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
    - Combine task lists, docs, spreadsheets, and chat in one
    - View and edit from mobile/offline
    - Cut down on emails

    Bit flags and bit flag manipulation is perhaps one of the most underrated strategies in programming, likely because most programmers developing in high-level languages rely too much on the high-level features, and forget about the low-level ones. Th…
    Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
    Hi everyone! This is Experts Exchange customer support.  This quick video will show you how to change your primary email address.  If you have any questions, then please Write a Comment below!
    Sending a Secure fax is easy with eFax Corporate ( First, Just open a new email message.  In the To field, type your recipient's fax number You can even send a secure international fax — just include t…

    759 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    10 Experts available now in Live!

    Get 1:1 Help Now