Question

Discrete Math Problems:

1. From the below algorithm (linear search) construct the function f(n) which computes the number of steps the algorithm executes for a list of n integers and compute O(f) using the definition

                    ALGORITHM 2 The Linear Search Algorithm.

                procedure linear search(x: integer, a1, a2,…, an: distinct integers)

                i := 1

                while (i ≤ n and x ≠ ai)

               i := i + 1

               if i ≤ n then location := i

               else location := 0

return location{location is the subscript of the term that equals x, or is 0 if x is not found}

2. For the algorithm below, can you construct f(n) which gives the number of steps performed with input n if so, construct f(n); otherwise state why not.

// input to algorithm is n, an integer

j := n;

while( j>= 1 )

{

   for i := 1 to j

      {

          x := x + 1;

       }

    j := floor ( j/2 );

}

Answer 1

Given:

ALGORITHM 2 The Linear Search Algorithm.

                procedure linear search(x: integer, a1, a2,…, an: distinct integers)

                i := 1

                while (i ≤ n and x ≠ ai)

               i := i + 1

               if i ≤ n then location := i

               else location := 0

return location{location is the subscript of the term that equals x, or is 0 if x is not found}

Linear Search number of steps:

If n = 1, number of steps= 1

If n = 2, number of steps= 2

…

If n=n, number of steps= n

So, f(n)=n.

Again,

// input to algorithm is n, an integer

j := n;

while( j>= 1 )

{

   for i := 1 to j

      {

          x := x + 1;

       }

    j := floor ( j/2 );

}

So, for n=1 number of steps=1

...

for n=8,

f(n)= 4 (while loop) + (8 + 4 + 2 + 1)(for loop) = 19

…

for n=n,