Big O notation For accessing middle element in linked list and binary search?

Article at http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html says that Big O notation For accessing middle element in linked list is O(N) .should not it be O(N/2) .Assume we have 100 elements in linked list So to access the 50th element it has to traverse right from first node to 50th. So number of operation will be around 50.

One more big notation defined for binary search is log(N). Assume we have 1000开发者_如何学JAVA elements. As per log(N) we will be needing the opeartion close to 3. Now lets calculate it manually below will be the pattern

500 th element, 250th, 125,63,32,16,8,4,2 so operation are around 9 which is much larger than 3.

Is there any thing i am missing here?

---

What you're is missing that any constant multiples don't matter for Big O. So we have O(N) = O(N/2).

About the log part of the question, it is actually log₂(N) not log₁₀(N), so in this case log(1000) is actually 9 (when rounding down). Also, as before, O(log₂(N)) = O(log₁₀(N)), since the two are just constant multiples of each other. Specifically, log₂(N) = log₁₀(N) / log₁₀(2)

The last thing to consider is that, if several functions are added together, the function of lower degree doesn't matter with Big O. That's because higher degree functions grow more quickly than functions of lower degree. So we find things like O(N³ + N) = O(N³), and O(e^N + N² + 1) = O(e^N).

So that's two things to consider: drop multiples, and drop function of low degree.

---

O(n) means "proportional to n, for all large n".¹

So it doesn't have to be equal to n.

Edit:

My explanation above was a little unclear as to whether something in O(n) is also in O(n²). It is -- my use of the word "proportional" was poor, and as the others were trying to mention (and as I was misunderstanding originally), "converge" would be a better term.²

_{1: It actually means "proportional to n when n is large in the worst-case scenario", but books usually consider the "average" case, which is more accurately represented by f(n) ~ n, where f is your function.}

_{2: For the more technical people: it should be obvious, but I am not intending to be mathematically rigorous. Math.SE might be a better choice for asking this question, if you're looking for formal proofs (with ratios, limits, and whatnot).}

---

From the web page you linked:

Similarly, constant multipliers are ignored. So a O(4*N) algorithm is equivalent to O(N), which is how it should be written. Ultimately you want to pay attention to these multipliers in determining the performance, but for the first round of analysis using Big-Oh, you simply ignore constant factors.

---

The Big O notation is a general expression of an algorithm's efficiency. You should not construe it as an exact equation for how fast an algorithm is going to be, or how much memory it is going to require, but rather view it as an approximation. The constant multipliers of the function are ignored, so for example you could view your example as O 1/2(N), or O k(N), drop the k which gives you O(N).