Question

What is the running time of the following algorithm (in the worst case) expressed in terms of n? for i 1 to n do if A[i] = x then return i elseif A[i] < x then i i + 1 else return ""x not found"" return ""x not found"" Select one: a. T(n) = n b. T(n) = n log n c. T(n) = 2n d. T(n) = n2

Answer 1

Answer: The worst case scenario is that x is not found in the array A, and the loop iterates n times. Within each iteration, there are a constant number of operations (comparisons and updates), so the running time of the algorithm is proportional to n. Therefore, the correct answer is:

a. T(n) = n

Step-by-step explanation: