In Computer Science there are various ways to solve a problem. Once you have alternative methods to choose from, it is always preferred to choose the best option. In Computer Science, the best option ususally means algorithm which takes less time or less space. It is generally, referred as time complexity and space complexity of the algorithm.

For this topic, I am going to cover only time complexity.

Efficiency of the program depends on how much time it takes to execute and provide accurate result. It is required to measure the growth rate of the program. It means, analyzing the time with respect to increase in input elements.

Let's try to understand this with the help of example.

You want to find a number from given 5 integer numbers. What are the alternatives to find a number 41 from given set of numbers {9, 3, 8, 5, 41}.

**Option 1:**

* *Iterate over the list of elements and check it one by one till the time you find the matching number.

It may be possible that you find the number at first place, if you are lucky. It may be possible that you get number in second comparison or may be third or may be fourth or may be fifth or may be not....

The best case is the one when you get the matching number in first attempt.

If you try 10 times, 100 times, 1000 times, it is possible that on an average you get matching number in 2nd or 3rd time. That is average case.

In worst case scenario, you have to check all numbers.

While comparing the algorithms, it is generally compared based on average and worst case scenario.

In the example above, what if you want to find a number from the set of 1000 numbers. In worst case, you will have to check all 1000 numbers. It means that the proposed solution has growth rate that depends on the size of the input elements. In mathematical terms if the number of elements is n, it will check n numbers. Number of comparison is increasing with increase in number of elements. Hence it is called linear function.

**Option 2:**

* *Assume that you have sorted set of elements. You have new sorted set {3, 5, 8, 9, 41} Now what...?

Start with the middle element and do comparison. If you find the number in first attempt, that is best case. But here middle element is 8. That is not the number you are searching (number 41). Since you know that this is sorted set of elements and hence you just need to check from the middle element to last element. You can simply ignore the other half of the set. Again apply similar logic to the upper half of the set. Continue till you find the elements or reach to a conclusion that number does not exist.

As you can see that in each attempt, number of elements is reduced by half. So in a set of 1000 numbers, the worst case scenario will be like this :

1. After 1st attemept, you are left with 500 numbers.

2. After 2nd attemept, you are left with 250 numbers.

3. After 3rd attemept, you are left with 125 numbers.

4. After 4th attemept, you are left with 62 numbers.

5. After 5th attemept, you are left with 31 numbers.

6. After 6th attemept, you are left with 15 number.

7. After 7th attemept, you are left with 7 numbers.

8. After 8th attemept, you are left with 3 number.

9. After 9th attemept, you are left with 1 numbers.

10. After 10th attemept, you know the result. Either you found the matching number or you know for sure that number does not exist in the given set of numbers.

As you can see that worst case scenario needs only 10 comparison versus 1000 comparison in Option 1.

In mathematical terms if the number of elements is N, it will check log_{2}N numbers. Hence it is called logarithmic function.

In computer science, this is also referred as Big O notation. It is a measure of growth rate of the function. Various functions are constant O(1), linear O(n), logarithmic O(log n) and quadratic O(n^{2}).

We will see each of this in next topic.

Java is a trademark of Oracle.

Apekshit.com is just for learning and testing. To improve basic understanding we provide some examples. We are constantly reviewing it to avoid errors, but we cannot warrant full correctness of all content.