TF Consider an application whose runtime can be expressed as nfn- 1) -n, where f
ID: 3716610 • Letter: T
Question
TF Consider an application whose runtime can be expressed as nfn- 1) -n, where f(1) is 1 plus the third digit of your student ID. Then, the running time of f is O(n2) Consider an application whose runtime can be expressed as f(n) f(n 1) -n, where f(1) is 1 plus the forth digit of your student ID. Then, the running time of f is O(n3). T F Consider an application whose runtime can be expressed as f(n) f(n -1) -n, where f(1) is 1 plus the fifth digit of your student ID. Then, the running time of f is O(n logn). T F Consider an application whose runtime can be expressed as f (n) f(n 1) -n, where f(1) is 1 plus the sixth digit of your student ID. Then, the running time of f is O(n!). T F 4Explanation / Answer
f(n) = f(n-1) - n
=> f(n-1) = f(n-2) - n-1
Substituting we get
= f(n) = f(n-2) - n-1 - n
=> f(n-2) = f(n-3) - n-2
Substituting we get
= f(n) = f(n-3) - (n-2) - (n-1) - n
........
f(n) = f(1) - Summation of n which is equal to n2
Hence f(n) = O(n2)
1) True
2) False
3) False
4) False
Constant term does . not matter , Digits of Student Id does not matter as it is just a constant.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.