What is meant by Best, worst and average case running times of an algorithm ???

In the simplest terms,

• Best case = fastest time to complete, with optimal inputs chosen.
  For example, the best case for a sorting algorithm would be data that's already sorted.
• Worst case = slowest time to complete, with pessimal inputs chosen.
  For example, the worst case for a sorting algorithm might be data that's sorted in reverse order (but it depends on the particular algorithm).
• Average case = arithmetic mean. Run the algorithm many times, using many different inputs, compute the total running time (by adding the individual times), and divide by the number of trials. You may also need to normalize the results based on the size of the input sets.

Complexity and running time are often expressed in "Big O notation," which is used to describe the approximate amount of time an algorithm requires to complete, based the size of its input.

The most commonly used Big O descriptions are

• O(1) always terminates in about the same amount of time, regardless of the input size.
• O(logN) takes a fixed additional amount of time each time the input size doubles.
• O(N) takes twice as long to finish if the input size doubles.
• O(N²) takes four times as long if the input size doubles.
• O(2^N) increases exponentially as the input size increases.

You can see from the table below that the difference is small for small input sizes, but it can become tremendous as the input size increases even a little bit.

Input Size              Time to Complete
               O(1)  O(logN)   O(N)   O(N2)   O(2N)
     1           1       1      1       1       1
     2           1       2      2       4       4
     4           1       3      4      16      16
     8           1       4      8      64     256
    16           1       5     16     254   65536

answer is copied from stackoverflow.com Read Here