- 1) You created a sorting algorithm. Its running time turned out to be O(n^2). How much better can you make this algorithm ? You do not know the nature of the data except the elements are of the same type.
- 2) Your employee delivered an algorithm for solving a task. You were told the running time is O(n^3). You have a large amount of data to run through this algorithm. Your boss wants to know how long it will take for you to run this algorithm on the entire data set. What kind of guarantees can you make to your boss ? Please use constant c if needed.
- 3) Your implementation of an algorithm has a running time of 9n^3 + 5n^2 -7n + 10. Your computer scientist contractor says the algorithm has Ω( n^2 ). Due to a large n,
n = 1.2 billion, your boss wants to reduce the running time down to O(n lg n). Can you guarantee your boss the execution of algorithm within his desire timeline ? (2 points) Justify your answer. Why can you ? or why can’t you ?
