Given an nelement array X of integers Algorithm C executes a

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(log n)-time computation for each odd number in X. What are the best-case and worst-case running times of Algorithm C

Solution

The best case is when all the numbers are odd. For each odd number in X it requires O(log n) time , so for all n elements it requires O(n log n) time.

THe worst case is when all numbers are even. For each even nuber it requires O(n) in X. Therefore total time requires is O(n *n)= O(n²).