For algorithms, a little memory outweighs a lot of time • Hacker News Board

Re: For algorithms, a little memory outweighs a lot of time

#141

Post by cwmoore » Sun, May 25, 2025, 11:17 PM UTC

jodrellblank wrote: post #125

ThomasBHickey wrote: post #101

Earlier quoted context omitted.

Try starting with a 2x2, then 3x3, etc. image and manually list all the possibilities.

That's focusing on the wrong thing; as I said, "I know it's 10 x 10 x 10 meaning 10^3 I don't need that explanation [for the correct combinations], what I'm looking for is an intuition for why it isn't 10x3".

ChatGPT might be able to explain combinatorics if you use the keyterm.

I’m fond of derangements and their relationship with permutations, which contain a factor of e.

Re: For algorithms, a little memory outweighs a lot of time

#142

Post by withinboredom » Wed, May 28, 2025, 12:04 AM UTC

Almondsetat wrote: post #140

withinboredom wrote: post #139

Earlier quoted context omitted.

Yes, but you are asserting the relationship is directly connected -- which is clearly not true. You said that it is O(n) memory and O(n) time, both using n. That means a program containing x bytes can only run for x seconds. This is clearly not true.

>That means a program containing x bytes can only run for x seconds. That is not what it means. Again, if you are not familiar with the notation then all you are doing is slapping your personal ideas about computing to some symbols

Hmm. Telling me I'm 'stupid' doesn't make you right.

Re: For algorithms, a little memory outweighs a lot of time

#143

Post by marojejian » Sat, May 31, 2025, 9:55 PM UTC

bbrubaker wrote: post #135

woolion wrote: post #73

It's unfortunate that Quanta links are so popular, when they include so much pseudo-poetic fluff around the mathematics. Below there's an entire thread to dismiss a misconception introduced by the quanta article. "I think it is very intuitive that more space beats the pants off of more time." (poster is absolutely right) The The article say "Until now, the only known algorithms for accomplishing certain tasks require…

I'm the author of this article. If you ask a complexity theorist, they will tell you that they did in fact have a general intuition that certain problems require space close to to linear in time to solve (see e.g., Ryan's comment #22 on Scott Aaronson's blog post about the result: https://scottaaronson.blog/?p=8680 , and the comments after that). The most intuitive way to see this is in a circuit/DAG picture, where t…

Thanks for the detailed response to that comment. I just read and enjoyed your article, and your response seems accurate.

I can imagine it's tough to put that much effort into communicating something complex to a wide audience, only to have a bunch of very smart people here attempt to tear it apart.

Re: For algorithms, a little memory outweighs a lot of time

#144

Post by bbrubaker » Tue, Jun 03, 2025, 6:01 PM UTC

marojejian wrote: post #143

bbrubaker wrote: post #135

Earlier quoted context omitted.

I'm the author of this article. If you ask a complexity theorist, they will tell you that they did in fact have a general intuition that certain problems require space close to to linear in time to solve (see e.g., Ryan's comment #22 on Scott Aaronson's blog post about the result: https://scottaaronson.blog/?p=8680 , and the comments after that). The most intuitive way to see this is in a circuit/DAG picture, where t…

Thanks for the detailed response to that comment. I just read and enjoyed your article, and your response seems accurate. I can imagine it's tough to put that much effort into communicating something complex to a wide audience, only to have a bunch of very smart people here attempt to tear it apart.

Thanks for the kind words! I do get lots of gratifying positive feedback as well. I don't make a habit of arguing with strangers online, but I felt obliged to correct the record here for anyone who might encounter this later and come away thinking "wow, I can't believe Quanta got it completely backward."

Here on HN people often complain about the level of detail, which is fair! I think they are often falling prey to a common fallacy about conditional probabilities. P("X reads Quanta"|"X has some technical background (college STEM major or more)") is likely larger than it is for most popular science magazine. But P("Y has some technical background"|"Y reads Quanta") is much lower than many people realize. There is a limit on how much technical stuff I can put in an article and still have it be accessible to many of our readers, and I care a lot about making things accessible.