Chapter 16.3, Problem 16.16CP

Explanation of Solution

The following algorithm is presented on checkpoint 16.15CP and its worst case complexity is discussed as follows,

Pseudocode:

Input: Two integer arrays “a[]” and “b[]” of size “n”.

Size of Input: The size specifies the number “n” of array entries.

Output: The condition is “true” of each element of “a[]” is also an element of “b[]” otherwise, it display “false”.

The following is the pseudocode for given data,

  Boolean Contains =true

  int i=0

  While Contains && i<n do

  Contains=Linearsearch(a[i],b)

  i++;

  End while

  Print Contains

Explanation:

• In the given code, set the Boolean variable “Contains” is equal to “true”.
• Execute the while loop if the condition is true,
  • The condition must be “i” less than “n” and the variable “Contains” must be “true”.
  • If it is true, then it calls for Linearsearch() function.
  • Increment the value of “i”.
• Thus, the while loop is executed until the condition satisfies and then finally it print the Boolean value either “True” or “False”.

Pseudocode for LinearSearch:

Input: An integer “X” and an array “b[]” of size “n”.

Size of input: The size specifies the number “n” of array entries.

Output: It returns true if “X” contains in “b[]”, otherwise “false”.

The following is the pseudocode for linear search,

Boolean LinSearch(int x, int[] b)

Begin

  int k=0;

  Boolean found =false;

  While !found && k<n do

  if(X==b[k])

  found =true;

  else   

  K++

  End If

  End While

Return found

End LinSearch

Explanation:

• The given code performs the linear search algorithm concept which process to find an item in an array...