Computer Science Algorithm
Computer Science Algorithm Homework
- 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 ?
-
No comments:
Post a Comment