Question

Determine the worst-case complexity of the algorithm in terms of n.

// search a key in an array a [1..n] of length n

for(int k = 1; k <= n; k++)

     if(a[k] == key) then return k;

return -1; // meaning key not found

Answer 1

for(int k = 1; k <= n; k++)             // Here this for loop iterates n times. O(n)
     if(a[k] == key) then return k;     // O(1)

return -1; // meaning key not found         // O(1)


Total  worst-case running time complexity is O(n)