Deadlines: first deadline 19th April, final deadline 30th April.
Submit your hand-in by Fire, in plain text, PDF or HTML format. For part 1 it is enough to fill in the table; for part 2 you should also write a short (one sentence) explanation of how you got your answer.
Part 1
Fill in the following table. For each function f(n) and time t, find the biggest size n that can be solved in time t, if the work takes f(n) microseconds. When the answer is big, you may write it approximately (e.g. 3.2×1011). A few of the answers are filled in to help you get started.
Hint: for each f, first solve the equation f(n) = t for n, then plug in particular values of t. A couple of the functions are hard to solve this way, and you may need to write a little program to find the answer. Feel free (but it is not compulsory) to write down how you solved the functions.
| f(n) | One second | One day | One year | The total life of the sun (≈ 14 billion years) |
|---|---|---|---|---|
10000 × log2 n |
1.3 × 1030 |
|||
1000√n |
||||
100n |
3.2 × 1011 |
|||
100n log2 n |
||||
10n2 |
||||
10n3 |
||||
0.001 × 2n |
||||
0.0001 n! |
17 |
Part 2
What is the complexity of the following functions? For the methods ex1 to ex6, write down a mathematical function T(n), depending on n, that counts how many addition operations the method executes. Then write down the complexity in big-O notation.
For ex7 to ex10, it is quite hard to calculate an exact number, so you need only write down the big-O complexity. It may help to write a recurrence relation like T(n) = O(n) + T(n-1) first.
You should also write one sentence for each example that explains why it has the complexity you found.
Make sure to read the loop lower and upper bounds carefully!