1

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)?

RandomGuy
  • 648
  • 6
  • 21

1 Answers1

4

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.

dee-see
  • 23,668
  • 5
  • 58
  • 91
  • Thanks! That makes a lot of sense (that link was also very helpful), especially when you transform it in 1/2 * N form. I knew that multiplying a constant or adding a constant to O(N) would simplify to O(N), but I wasn't sure about a division since I never calculated this case before. I also didn't think in transform the division in a multiplication. This added to my idea that log(n) is usually an algorithm that doesn't run over all cases led me to think that O(N/2) could someway resolve to O(log n). – RandomGuy Mar 11 '18 at 00:02