Problem
1. Given an n-element array X, Algorithm B chooses logn elements in X at random and executes an O(n)-time calculation for each. What is the worst-case running time of Algorithm B?
2. Given an n-element array X of integers, Algorithm C executes an O(n)-time computation for each even number in X, and an O(logn)-time computation for each odd number in X. What are the best-case and worst-case running times of Algorithm C?