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).

Finding Time Complexity (Asymptotic Analysis)

There are some basic code statements that are used to build complete program. It is necessary to know their time complexities in order to calculate the time complexity of whole code/algorithm.

We will look at them one by one-

1. Constant Time [O(1)]

1
2
3
4
5
6

void sum() {
int a= 2;
int b=3;
int c = a + b;
System.out.println(c);
}

In above code we are not taking any input. So this code is independent of input size. Lets say the above code takes time C to execute. This time will always be constant irrespective of the input size. In asymptotic analysis we say that the time complexity is O(1).

2. Simple Loops

1
2
3
4
5
6

int k= 0;//time c1 
// loop will execute n times 
for(int i = 1 ; i<=n ; i++)
 {
 k= k+ i; //time C2 
}

Total time = Time taken by initialization statement  + Time taken by statements inside loop x Number of time loop will execute
Total time = C1 + C2 x n
Total time = C1 + C2n i.e. O(n)

3. Nested Loops

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int k= 0, m = n; //time C1

// outer loop will execute n times
  for(int i = 1 ; i<=n ; i++) {

   k= k+ i; //time C2

// inner loop will also execute n times
for(int j = n ; j>=1 ; j--) {

   m= m- j; //time C3
    
}
}

In nested loops we analyze time from inside out. 

Time taken by inner loop = C3 x n

Total time  = Time taken by initialization statement + Time taken by statements inside outer loop x Number of time outer loop will execute
Total time = C1 + (C2 + C3n) x n
Total time = C1 + C2n + C3n²   time  i.e. O(n²) 

4. Consecutive Statements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int x = 0, k=0; //time C1

// loop will execute n times
  for(int y = 1 ; y<=n ; y++) {

   x= x+ y; //time C2
     
}

// outer loop will execute n times
  for(int i = 1 ; i<=n ; i++) {

   k= k+ i; //time C3

// inner loop will also execute n times
for(int j = n ; j>=1 ; j--) {

   m= m- j; //time C4
     
}
}

Total time =  C1 + C2n + (C3 + C4n) x n
Total time =  C1 + C2n + C3n + C4n² 
i.e. O(n²) 

5. If else statements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

boolean bool; //time C1

if(bool) {
  return true; //time C2
  
}
else {

// loop will execute n times
  for(int y = 1 ; y<=n ; y++) {

    y++; //time C3
     
}

}

Here we check for worst case scenario
(remember general rules? ) i.e. what will be the larger time complexity?

Total time will be either C1 + C2 in case 'if' condition is true. Or it will be C3n in case else statement executes. So, maximum time complexity in worst case would be O(n).

6. Logarithmic

1
2
3
4
5

 for(int i = 1 ; i<=n ; i++) {

   i= i*2; //time C

}

Here value of i is becoming twice in every execution and hence reducing the number of times the loop will execute. Let's see how it goes-
Initially i = 1 i.e. 2⁰
Execution 1 -> i = 2 i.e. 2¹
Execution 2 -> i = 4 i.e. 2²

Execution 3 -> i = 8 i.e. 2³

Execution 4 -> i = 16 i.e. 2⁴ and so on...

Lets say 2^k = n. If we take log on both side to the base 2, we get
log2^k = logn
k.log2 = logn
k = logn (since log2 to the base 2 is 1)

k is nothing but the total time taken by loop and hence time complexity is O(logn).

Asymptotic Notations- Big Omega Notation [Ω] & Big Theta Notation [Ѳ]

In the previous post we have seen the 1. Big O Notation [O]. Next is-

2. Big Omega Notation [Ω]

In opposite to the big O notation this notation represents tightest lower bound of the given function.

Analytically we say as: f(n) belongs to Ω(g(n)) as there exists c > 0 (e.g., c = 1) and n0 (e.g. n0 = 5) such that f(n) ≥ c.g(n) whenever n ≥ n0.

Example- lets find tightest lower bound of f(n) = 5n²+2n+1.

By looking to f(n) we can say that if we have a function g(n) = n²  (As, n²  is always less than 5n²) then it will be the tightest lower bound of f(n). In other words: f(n) ≥ c.g(n) for c=1 & n0=1. In Big Omega, we say f(n) = Ω(n²) & it is read as "f of n is big omega of n²".

Another thing to note is if f(n) = Ω(n²) then f(n) = Ω(n) or f(n) = Ω(logn) because n & logn are lesser than n²

But since we use Big Omega notation to represent tightest lower bound of the function, we will say f(n) = Ω(n²) instead of Ω(n) or Ω(logn).

Big Omega notation is usually used to specify time/space complexity of the given algorithm in best case scenario. Best case scenario is the situation when algorithm takes the least time to run or the least memory during it's execution.

3. Big Theta Notation [Ѳ]

This notation is used to find average time/space complexity of an algorithm.

Average complexity will always be between tightest upper bound and tightest lower bound.

Analytically we say as: f(n) belongs to Ѳ(g(n)) as there exists c > 0, d > 0 (e.g., c = 1, d=3) and n0 (e.g. n0 = 5) such that c.g(n) ≥ f(n) ≥ d.g(n) whenever n ≥ n0.

Example- suppose, we have a function f(n) = 7n³+2.
Then f(n) = O(n³) for c = 8, n0=2. Also, f(n) = Ω(n³) for c = 6, n0=2. Now as lower & upper bound of f(n) is n³ then we can say average of time complexity for f(n) is n³. Hence, f(n) = Ѳ(n³) & it is read as "f of n is big theta of n³".

General rules while analyzing time complexity:
1. We analyze the time complexity for very large input size.
2. We consider worst case scenario i.e. Big O notation.
3. For any function, f(n) then we drop lower order terms & constant multipliers.
e.g. f(n) = 10n⁴+4n³+n²+2n+5 then f(n) = O(n⁴)
Here, we have dropped lower order terms which are 4n³,n²,2n & 5. We have considered 10n⁴ and finally we omitted 10, which is a constant multiplier & we are left with n^4.