Question

 public int linearSearch2(ArrayList<Integer> pList, Integer pKey) {
      for (int i = 0; i <= pList.size() / 2; ++i) {
          if (pList.get(i).equals(pKey)) {
              return i;
          } else if (pList.get(pList.size() - 1 - i).equals(pKey)) {
              return pList.size() - 1 - i;
          }
      }
      return -1;
  }
-----
Q1)Which function f(n) counts how many times the key operation(s) is(are) performed as a function of the list size n when pKey is not in pList (the worst case behavior of linearSearch2() occurs when pKey is not found)? Note that when n is a number, ⌊n⌋ is called the floor of n and is defined to be the largest integer that is less than or equal to n. For example, ⌊8⌋ = 8, ⌊8.2⌋ = 8, ⌊8.9⌋ = 8, ⌊8/2⌋ = 4, ⌊7/2⌋ = 3. 

a.) f(n) = ⌊n / 2⌋²
b.) f(n) = 2n
c.) f(n) = n ⋅ log(2 ⋅⌊n / 2⌋)
d.) f(n) = n
e.) f(n) = n / 2
f.) f(n) = 2 ⋅ ⌊n / 2⌋ + 2

-----
Q2) Continuing the questions about linearSearch2(). What is the worst case time complexity of the algorithm?

a.) O(n)
b.) O(n lg n)
c.) O(1)
d.) O(n²)
e.) O(2n + 2)

Answer 1

Solution:

 public int linearSearch2(ArrayList<Integer> pList, Integer pKey) {
      for (int i = 0; i <= pList.size() / 2; ++i) {
          if (pList.get(i).equals(pKey)) {
              return i;
          } else if (pList.get(pList.size() - 1 - i).equals(pKey)) {
              return pList.size() - 1 - i;
          }
      }
      return -1;
  }

See, in the worst-case pKey is not in the pList, this means that every time if and else both the statements will be executed.

The loop is running n/2 number of times and each time 2 key operations are executed, this means that n/2*2= n

d.) f(n) = n is the correct answer.

2)

O(n) is the worst-case time complexity here.

Hit the thumbs up if you liked the answer. :)