i) find a specific value in the data structure
ii) delete this value from the data structure
iii) insert some other value, at the appropriate place, into the data structure
Consider each of the following data structures as a candidate for the above myTask, which involves performing all three operations. For each data structure, state the overall BIG-OH for myTask in terms of the average case and the worst case as a function of n, where n is the number of elements in the data structure. Do NOT guess: +2 points for correct answer, -2 points for incorrect answer, 0 points for no answer.
| myTask: Big-Oh | ||
| Average Case | Worst Case | |
| Unsorted Array | ||
| Sorted Array | ||
| Minheap (Priority Queue) | ||
| Binary Search Tree | ||
| Hash Table | ||
b) Independent of language, what operator type(s) would be best to handle an operation with three operands.
c) Program a function, in C, which is given three boolean parameters, and returns true (1) if at least two of the operands are "true".
The prototype is: int atLeastTwo(int a, int b, int c)
Use any C operators but NO other constructs (such as IF).
a) Write a recurrence relation for M(n), the number of multiplications performed. Do not solve the recurrence. Note that n can be any nonnegative integer.
int pow(float x, unsigned int n)
{
if (n == 0) return 1;
if (n == 1) return x;
if ( (n % 2) == 0 ) return pow(x*x, n/2); // n is even
return x*pow(x*x, n/2); // n is odd
}
b) Determine M(2007).