/sci/ - Science & Math » Thread #13561266

6KiB, 312x135, asdfdiscuss.png

View Same Google iqdb SauceNAO

Anonymous Wed 25 Aug 21:22:13 2021 No.13561266 View Reply Original Report

Quoted By: >>13561281 >>13562178 >>13562194

How does /sci/ deal with floor and ceils in solving recurrence relations via substitution. In the book Introduction to Algorithms by CLRS they say that the floor and ceils are "Usually ignored" and they are in the solutions in the book.

However I do see some adding a +1 to the ceil term(that is if we have ceil(n/2) it becomes (n/2+1) in the induction.

What are the consequences of factoring in floors and ceils or simply ignoring them?

Anonymous

Anonymous Wed 25 Aug 2021 21:30:34 No.13561281 Report

Quoted By:

>>13561266
You ignore them because most of the time you're looking for asymptotics, and the ceil/floor function doesn't alter the behavior of anything at infinity. I may be wrong though.

Anonymous

Anonymous Thu 26 Aug 2021 02:22:00 No.13562178 Report

Quoted By:

>>13561266
Dude you literally made a thread earlier about this. The ceil and floor make sense for bounds or parity arguments, but they don't affect your asymptotic analysis since at most you're off by 1, and any nonconstant functions you have in your expression will either grow way past or decay way faster (you'll study o(1) functions for expectation or concentration in random algorithms),
>What are the consequences of factoring in floors and ceils or simply ignoring them?
You have to understand *why* they're present but why certain types of algorithm analysis ignore them. They matter when we're trying to specify steps for an algorithm where parity or being in bounds matters, but being at most 1 off of n / 2 for n large changes literally nothing asymptotically

Anonymous

Anonymous Thu 26 Aug 2021 02:24:51 No.13562194 Report

Quoted By:

>>13561266
>How does /sci/ deal with floor and ceils in solving recurrence relations via substitution
Take a look at how they're used in these bounds:
>>13560074
Notice how the sums change slightly when you use floor and ceiling, but if you're careful with your less than or greater than signs, you can stare and see that you get essentially the same answer than if you didn't have them.

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches