Find out the c and n0. Please explain with the steps.
Asked
Active
Viewed 75 times
-7
-
1Forget about the algorithm. It's a question of how it can be proved mathematically. – Venkatesh K Oct 16 '16 at 21:35
-
2If the time taken is proportional to (n+1)⁵, then it's O(n⁵) by definition. What's to prove? – Jon Hanna Oct 16 '16 at 21:37
-
3Expand (n+1)^5 and your answer falls out easily. – GManNickG Oct 16 '16 at 21:37
-
I need the value of c & n0 – Venkatesh K Oct 16 '16 at 21:40
-
1@vengets: There are many ways to do this, and no correct way, so I don't think it's a very good fit. Also you don't explain what c and n0 are. Not everyone uses the same letters, so how do you expect people to know what you mean. – Chris Beck Oct 16 '16 at 21:46
1 Answers
2
limit as n --> infinity of (n+1)^5 / n^5 = 1.
This is neither 0 nor infinity, so they have the same complexity. This complexity is traditionally written as O(n^5).
This does assume that each step is constant for whatever you are measuring.
Gordon Linoff
- 1,242,037
- 58
- 646
- 786
-
-
1OP, note that this holds for any value of *c* and *n*. Pick a number, any number. – drew moore Oct 16 '16 at 21:44