.

3. (15 points) For n distinct elements a1,,an with positive weights w1,,wn s.t. i=1nwi=1, design a linear-time algorithm returning the element ak, which satisfies the following: aiakwi1/2. Assume that such an ak always exists. You should also justify the time complexity