1
I’m having difficulty in this exercise of complexity of algorithms, someone can give a light?
Prove that if f(n) = -n then f(n) is O(1).
One idea I had was that for any positive n, f(n) will be less than n. I don’t know if it’s correct
1 answer
1
All f(n) does is return -n. Calculating the negative of a number is a constant complexity operation, it is equal for all numbers. And a constant complexity algorithm (large or small) is O(1).
Browser other questions tagged algorithm mathematics
You are not signed in. Login or sign up in order to post.
"for any positive n, f(n) shall be less than n", I don’t see how that can affect the complexity of the algorithm. In this case, I think it would be enough to comment that the number of operations performed to calculate the output is constant, so it is O(1).
– Woss
I think I get your point, but what to "prove" it? Wouldn’t have to have some mathematical language?
– Bakun
@Bakun, just show that the amount of executed operations is not affected by the size of the input. That is, by the way, the definition of
O(1)– Jefferson Quesado