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

}