Design analysis and algorithm Program 2

 

2.     Consider the searching problem where:

 Input: A sequence of n numbers A = <a1, a2, …, an> and a value v.

 Output: An index i such that v=A[i] or the special value NIL if v doesn't appear in A. Write pseudo code for linear search and implement by using any programming language, which scans through the sequence, looking for v.

Solⁿ:

Pseudocode:

1.      Input the Numbers in an array . Let the numbers in array is A.

2.      Input the value V.

3.      let c=0

4.      for( i=1;i<=n;i++)

{

            If(A[i]==V)

            {

                        Print(The Number is found at i);

                        c=1;

                        Break;

            }

}

If(c==0)

{

            Print("The Number is not found in the array");

            Print(" So the Value is NIL");

                                    }

5.      End of Program.

Linear search(A):             

cost      times

a.       for i = 0 to n-1                    C₁        n

b.      if V = = A[i]                       C₂        (n-1)

c.             return i                          C₃        1

d.      return -1                             C₄        1

Time complexity:

Worst case:

T(n)      = C₁* n + C₂ * (n-1) + C₃ + C₄

= (C₁+C₂) * n - (C₂-C₃-C₄)

= a*n – b         (where a = (C₁+C₂)_, b = (C₂-C₃-C₄) )

= O(n)

Best case:-

T(n)      = Ω(1)

Average case:-

T(n)      = (n+1) / 2