RandomGuy
Reputation: 667
Does O(N/2) simplifies to O(log n)?
I have one algorithm that only needs to run in O(N/2) time (basically it is a for loop that only runs over half of the elements).
How does this simplifies in the big O notation? O(log n)?
Upvotes: 1
Views: 986
Answers (1)
dee-see
Reputation: 24088
Big O notation drops the factors. O(N/2) = O(1/2 * N) and simplifies to O(N).
If you want to know why the factor is dropped I would refer you to this other SO question.
Upvotes: 4
Related Questions
- Is O(log n) always faster than O(n)
- Does 2 ^ O(log log n) = O(log n)?
- n^2 log n complexity
- Why is O(n/2 + 5 log n) O(log n) and not O(n log n)?
- Is time comlexity O((log(N))^2) equivalent to O(sqrt(N))?
- O(log n) clarification
- Time Complexity: O(logN) or O(N)?
- Why O(2^log(n)) = O(n) and it is not a exponential run time?
- N log(N) or N clarification
- Is O(1/2 X log N) = O(logN)