In page 48 of lesson 22's presentation, "Time Complexity of Local Means and Local Medians", it says that the select function can find the median value in linear time O(n). Is this right? I believe that "select" has a worst case time of O(n^2) and probably an average time of less, but why O(n)? Making the "greater" / "smaller" list is done in O(n), so actually we can't say nothing on the average case besides that it's between O(n) and O(n^2) (with possible equality).

Having that said - shouldn't the use of sorting provide better result for the local median algorithm?

Please read carefully and quote carefully.

The slide says

"But faster median finding, running in time which is **linear in
the number of items**, is known (you saw it in the recitation, named

select(lst,k)). This will then be $O(k^2)$ steps too.''

and it refers to the time to find median in the (2k+1)-by-(2k+1) window.

Neither $O(n)$ nor $O(n^2)$ is relevant here.

In class I said that for small values of k, it will probably be better to simply

sort the items in the window than using a fancy median finding algorithm, even

though asymptotically (for large values of k) the latter would be better.

Benny

There must be some misunderstanding on my side :)

Can you please clarify why is "select" linear to the number of items?

Thanks!

the worst case for this algorithm is O(n^2). by "Linear" Benny means O(n), which is the intermediate case for this algorithm: if your list is long (K is large, a bigger square is used and you have to find the median among a large list), you should better use Select, but for small values of K, you may use regular sort: sort all the list and return the median.

I must say that this thread managed to confuse me a great deal… seems like Amit and Benny's comments slightly contradict each other, would be very nice if someone could clarify it once and for all before tomorrow:)

If I understood correct(and I highly doubt it right now), Benny says that the running time is linear to the number of items -In the window on which we calculate the median- so double window size will translate to double running time. As for what Amit says, it seems to me like he's saying that the running time is NOT linear to the number of items in the worst case - O(n^2)

(additionally, I assume that all the k's and n's were actually referring to the same thing, right?)

So… what is going on here:/

as for what I said - you may look in the page titled:

"זמני ריצה של אלגוריתמים רקורסיביים"

K is not n.

K is a parameter used in the Local Medians algorithm: K=1 means you calculate using any number in a square made of going one step to each direction. K=1 means: 8 numbers around, K=2: 24 number around, etc… (defines the size of the square)

n is the number of items among which you want to find the median.

e.g: if K=1, you need to find the median among 9 numbers (the number in the center and the 8 numbers surrounding it): then n=9… if K=2, n=25… etc (In general, n it the length of the list!)

I don't see the contradiction between what we said, but let's leave it to the professionals :)

Oh if that's what you mean by n, then shouldn't it be O(dimensions of matrix) worst case?, which is n^2 only if matrix is square?

And then what you say is trivial, obviously you must go through every item in order to calculate a median for every item….