[General boards] [Winter 2019 courses] [Fall 2018 courses] [Summer 2018 courses] [Older or newer terms]

Why is evaluation of piecewise poly for 1 data point O(1)?


#1

(slide 240)

If we know which range the given point is in, it’s O(1).

The place where I’m stuck is how do we know which range to go with in O(1) time?

I can’t think of a way to use hash tables and the only data structure I can think of is a tree which would be O(log(n)) to find which part of the piecewise poly to use.


#2

It’s O(1) for each data point. It’s O(1) because the line for each interval is simply defined by two points.


#3

TLDR: just think O(!)

This is resolved! Thank you for your reply! :slight_smile:

Let me try to explain what I’m stuck on with an example.

Let’s say we have a linear spline.
L(x)
= x if 0<= x < 2
= 2x if 2 <= x < 4
= 3x if 4 <= x < 6

Now, we want to evaluate L(2.5).

What kind of algorithm can we use in O(1) time that will tell us to use the [2,3) domain?

I realized that it’s basically just bucket sort (so bucket search?)

We obviously don’t need to know this for the exam but I thought this a cool and simple thing I’ve never learned.

so in the example above, we have 4 buckets with indices [0,1,2,3]
formula: (floor(x) / max key value) * # of buckets
x = 2.5: (floor(2.5) / 6) * 3 = 1 (yay!)
x = 4.6 (floor(4.6) / 6) * 3) = 2 (yay!)

This is the O(1) operation to find the bucket.

Way better than binary search.


#4

It is nice to see connections between this course and other ones.

Let me add a few things.
Indeed, bucket search is enough if the spline knots are equidistant.
And I assume that, by “bucket search”, we mean the first placement of the array elements in buckets, and not the recursive call to it to eventually sort the elements.
This is because in the spline case, we only need to know which subinterval (bucket) each element (evaluation point) belongs.

I should also add that, in most realistic cases of using spline interpolation, the evaluation points (which are the array elements)
are already given in sorted form, and their number is quite larger than the number of knots.
In those cases, for each evaluation point (going in ascending order), one (or at most two) comparisons are enough to place it in the correct bucket (subinterval), even if the knots are not uniform.

Aside of this, the L(x) you defined above is a linear pp, but not a linear spline, as it is discontinuous.