- Forum
- General C++ Programming
- Expressing this functions in terms of bi
Expressing this functions in terms of big-o-notation
Express the function n3/1000 - 100n2 - 100n+3 in terms of Θ-notation.
Trying to understand how to calculate such a function, It was in CLRS book as an exercise and idk how that's solved, so.. steps would be great ^-^
Trying to understand how to calculate such a function, It was in CLRS book as an exercise and idk how that's solved, so.. steps would be great ^-^
Last edited on
big-o is a bit weird to come up with the FORMAL answer.
Here, if N is large enough, you only need the dominate term. If N is quite small, you need more. The constants more or less vanish.
For large N, that is simply O(N^3)
because if N were 1 billion, 1B^3 is so much bigger than 100^1B^2 that the second term is lost in the first, its absorbed.
Here, a small N does not make sense. Big O is about how many operations the CPU performs to execute an algorithm. If N were 5, you get a negative answer, which makes NO sense. Technically I think you can abs() the thing and come up with O(N^2) for the work done, but I do not recall what you do when the value is negative. I have never seen a negative number of steps executed algorithm, so methinks your equation is incorrect.
Here, if N is large enough, you only need the dominate term. If N is quite small, you need more. The constants more or less vanish.
For large N, that is simply O(N^3)
because if N were 1 billion, 1B^3 is so much bigger than 100^1B^2 that the second term is lost in the first, its absorbed.
Here, a small N does not make sense. Big O is about how many operations the CPU performs to execute an algorithm. If N were 5, you get a negative answer, which makes NO sense. Technically I think you can abs() the thing and come up with O(N^2) for the work done, but I do not recall what you do when the value is negative. I have never seen a negative number of steps executed algorithm, so methinks your equation is incorrect.
Topic archived. No new replies allowed.