- Forum
- General C++ Programming
- Big O notation help
Big O notation help
Just need a little clarification between these two big O notation functions. Which is more efficient and why?
O (n^2) vs. O (n (n-1)/2)
O (n^2) vs. O (n (n-1)/2)
They are the same: leading terms are equal to n^2.
Read this http://en.wikipedia.org/wiki/Big_O_notation#Infinite_asymptotics
Read this http://en.wikipedia.org/wiki/Big_O_notation#Infinite_asymptotics
I might be horribly wrong at this, but isn't it like this?
O(n(n-1)/2) = O( (n^2 - n)/2)
So O(n(n-1)/2)<O(n^2) for x<-1 and x>0
.. and since we're looking at x>0 only, O(n(n-1)/2) is always lower, and therefor more efficient.
O(n(n-1)/2) = O( (n^2 - n)/2)
So O(n(n-1)/2)<O(n^2) for x<-1 and x>0
.. and since we're looking at x>0 only, O(n(n-1)/2) is always lower, and therefor more efficient.
Last edited on
@tfityo
See that's what I thought, since they're both n squared they should be equal, but then I was wondering, what about the division of 2? would that cut that one in half and make it smaller?
See that's what I thought, since they're both n squared they should be equal, but then I was wondering, what about the division of 2? would that cut that one in half and make it smaller?
There is no point to write O(n^2 - n), since n << n^2 if n -> infinity, so preferable notation is O(n^2).
Also, constant factors are often omitted since they depend on many details and may be different on different computers, therefore O(n^2/2) = O(n^2).
But if you have the same operations in both cases then you are right: n^2 multiplication is worse than 1/2(n^2 - n) multiplications.
Also, constant factors are often omitted since they depend on many details and may be different on different computers, therefore O(n^2/2) = O(n^2).
But if you have the same operations in both cases then you are right: n^2 multiplication is worse than 1/2(n^2 - n) multiplications.
Topic archived. No new replies allowed.