Given an nelement array X Algorithm B chooses log n elements

Given an n-element array X, Algorithm B chooses log n elements in X at random and executes an O(n)-time calculation for each. What is the worst-case running time of Algorithm B

Solution

Answer:

To choose an element randomly , it takes constant time .So overall selecting an element from array take constant time .Now , with each element algorithm B performs O(n) task.So element chosen logn in number and each has O(n) task , so total is n*logn .Therefore the worst case runnig time of B is O(nlogn).