Question

Given the following algorithm:

Algorithnm Input: a1, a2,...,an, a sequence of numbers n, the length of the sequence x, a number Output: ?? i:- 1 While (x2 # a, and i < n) i+1 End-while If (x- - a) Return(i) Return(-1) 3, -1, 2,9, 36,-7, 6,4 a) What is the correct output of the Algorithm with the following input: a1, a2,..an b) What is the asymptotic worst-case time complexity of the Algorithm?

Answer 1

a) The output is -1. Here x = 4, so x² = 16. Now the algorithm compares x² with all the elements of the input sequence (3, -1, 2, 9, 36, -7). Since none of them is equal to 16, the while loop keeps running until i = 6. At this point the condition i < n is no longer satisfies and thus the while loop break and since a₆ = -7 which is not equal to 16, so -1 is printed.

b) Worst case happens when no element in the input sequence is equal to x². If this is the case, the while loop keeps running until i = n, at which point the condition i < n is no longer satisfied and thus the loop breaks, All other operations except the loop are constant time i.e. O(1). Now, since the variable i increments by one in every iteration of the loop, so there are n possible iterations of the loop in worst case. Thus , the time complexity in worst case is O(n).