 |
.. (לתיקייה המכילה) | |
Last Update: 21.11.2011
- 21.11: Added 3,4.
- 16.11: Added 1,2.
- 21.11: Added 3,4.
- 16.11: Added 1,2.
1. Question 1: What does the question require? | |
|
In this question, you need to order the 14 functions with respect to the O symbol and prove your answer. In case you have two functions fi,fj such that fi = Θ(fj), prove so. For example, if the functions are: f1 = n^2 f2 = log(n) f3 = n log (n) f4 = n^2 + n log(n) then the correct answer is f2, f3, f1 = Θ(f4). Notice that since O is transitive (if f = O(g) and g = O(h) then f = O(h)), you would only need to show in the example that f2 = O(f3), f3 = O(f1) and f1 = Θ(f4). |
2. Question 5: Can we assume that M is known in advance? | |
|
No. M can change throughout the course of the data structure, and is unknown in advance. (Reminder: M is the total number of non-zero entries in all k matrices.) |
3. Question 2c: What can we assume on f1(n), f2(n), g1(n) and g2(n)? | |
|
Assume that all 4 functions are from N (set of natural numbers) to N. That is, f1(n), f2(n), g1(n) and g2(n) return non-zero integers, and therefore f1(n)/f2(n) and g1(n)/g2(n) are well-defined. |
4. Question 5: Why does Get(mat,i,j,val) receive a "val" parameter? | |
|
It's a copy-paste mistake made by us, the function should not receive a "val" parameter. The files were corrected accordingly. |