1. Briefly describe a bit-vector, giving details about
Give an example of a set and its representation as a bit-vector. [3]
2. What is the best-case and worst-case time complexity of the add() and intersection() operations for a Set ADT, if implemented with an array? (no explanation no marks). [4]
3. What are the main advantages and disadvantages of an array-based implementation of the Set ADT compared to a bitvector-based implementation? State the advantages and disadvantages as separate sections for each. [3]
1. What is normally meant to be the input size if the algorithm’s input is i) an integer (numeric algorithm), ii) collection of elements or iii) a string? What do we count when calculating the time complexity of an algorithm? [3]
2. Assuming that f(n) = O(logn) and g(n) = O(nlogn), what should be f(n) * g(n)? Why? Simplify the resulting expression. [3]
3. What is the worst-case time complexity of this function? Explain. When providing your analysis, don't forget to specify what is the input size. [4]