Linear Search In Java And It's Complexity

As name says , linear search is searching for an element in the data structure in a linear or sequential fashion. Suppose I have a bag containing 20 balls which are having any random numbers from 1 to 100 printed on them. Then, how I can find the ball with number, say  55? If we use linear search then we will take out one ball at a time and check a number on it till we find the one with number 55.

Let’s implement linear search in java-

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/** * LINEAR SEARCH JAVA PROGRAM */ package javagreedy.blogspot.com; /** * @author javagreedy.blogspot.com * */ public class LinearSearchApp { public static void main(String[] args) { int[] bag = new int[] { 10, 33, 23, 75, 98, 22, 44, 37, 55, 67, 13, 64, 80, 36, 74, 68, 12, 92, 15, 20 }; // bag containing 20 numbers linearSearch(bag, 55); // search 55 in bag linearSearch(bag, 29); // search 29 in bag } private static void linearSearch(int[] bag, int numToFind) { // scan complete bag for (int i = 0; i < bag.length; i++) { // check element one by one if (bag[i] == numToFind) { System.out.println("Bingo!! " + numToFind + " is found at location " + i); return; } } System.out.println("Oops! Bag doesn't contain " + numToFind + " at all!"); } }

Output:
Bingo!! 55 is found at location 8
Oops! Bag doesn't contain 29 at all!

What is the time complexity of linearsearch?

Worst  Case:  See the second execution of above program where we searched for number, 29 till last element in array and we didn’t find it. This is the worst case when number is not present in the array.  For 20 array elements we checked (line number 27) 20 times. So, if we have ‘n’ number of elements in bag then we will have to check for ‘n’ times. So, worst case complexity will be O(n).

Best Case: What if we found the number on the first check itself? Well, you guessed it right; it’s the best case for linear search. Irrespective of the number of elements in an array we will always have to check for a number only once if it's the best case. So, best case complexity becomes O(1).