Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A curious case of O(N^2) behavior which should be O(N) (2023)

gist.github.com

Post reply on HN
Print view View original

11–20 of 46 posts

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#11

Post by EdSchouten »

bla3 wrote: post #6
Liftyee wrote: post #3

Neat find! This proves to me a huge benefit of open source software: individual developers can satisfy their curiosity towards particular issues (with additional motivation from being personally affected) and improve the package for everyone once it's fixed.

Except it wasn't improved in this case, if I'm reading the gist correctly. The author didn't like their fix enough to make a pull request.

Just like “this entire meeting could have been an email”, all this effort writing this gist could have been spent creating a PR.

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#12

Post by dgfitz »

samatman wrote: post #10
Sharlin wrote: post #2

More accidentally quadratic stories: https://www.tumblr.com/accidentallyquadratic

A classic. Every time I see that link I read the whole thing starting from the new beginning. ...oops

I opened the link and just started reading. I have a really dumb question that may expose common knowledge I don’t have, about this quote:

> The total amount of space needed to represent this collection of strings is O(k n^2).

I haven’t seen O-notation ever represent ram usage, just algorithm complexity. Is this common?

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#13

Post by nneonneo »

dgfitz wrote: post #12
samatman wrote: post #10

Earlier quoted context omitted.

A classic. Every time I see that link I read the whole thing starting from the new beginning. ...oops

I opened the link and just started reading. I have a really dumb question that may expose common knowledge I don’t have, about this quote: > The total amount of space needed to represent this collection of strings is O(k n^2). I haven’t seen O-notation ever represent ram usage, just algorithm complexity. Is this common?

Yes, very common. You've seen "time complexity"; it's very common to talk about "space complexity" as well.

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#14

Post by geuis »

"Now, it should be clear that most of the time (28s-53s on the time line) of importing that particular USD file is spent in id_sort_by_name".

Luckily there's a graph screenshot. But the graph it displays is incomprehensible. Without "id_sort_by_name" being on the one bar, I wouldn't even know what I'm looking at.

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#15

Post by itronitron »

samatman wrote: post #10
Sharlin wrote: post #2

More accidentally quadratic stories: https://www.tumblr.com/accidentallyquadratic

A classic. Every time I see that link I read the whole thing starting from the new beginning. ...oops

Is there a way to do that without signing in?

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#17

Post by wtallis »

geuis wrote: post #14

"Now, it should be clear that most of the time (28s-53s on the time line) of importing that particular USD file is spent in id_sort_by_name". Luckily there's a graph screenshot. But the graph it displays is incomprehensible. Without "id_sort_by_name" being on the one bar, I wouldn't even know what I'm looking at.

The timeline view in the upper screenshot is fairly straightforward: the region of 28-53s is selected, other parts of the timeline are grayed out, and the statistics for the selected time region down below show 94.4% of "Total CPU" being in id_sort_by_name.

The lower screenshot is a flame graph. If you haven't encountered one of those before, it's totally reasonable to not know how to read it. But it's a standard and common way to present this sort of data. See https://www.brendangregg.com/flamegraphs.html for more information.

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#18

Post by consp »

nneonneo wrote: post #13
dgfitz wrote: post #12

Earlier quoted context omitted.

I opened the link and just started reading. I have a really dumb question that may expose common knowledge I don’t have, about this quote: > The total amount of space needed to represent this collection of strings is O(k n^2). I haven’t seen O-notation ever represent ram usage, just algorithm complexity. Is this common?

Yes, very common. You've seen "time complexity"; it's very common to talk about "space complexity" as well.

Fun bonus: they can be interchangeable, e.g. increasing space to reduce time.

Re: A curious case of O(N^2) behavior which should be O(N) (2023)

#20

Post by dgoldstein0 »

consp wrote: post #18
nneonneo wrote: post #13

Earlier quoted context omitted.

Yes, very common. You've seen "time complexity"; it's very common to talk about "space complexity" as well.

Fun bonus: they can be interchangeable, e.g. increasing space to reduce time.

Yes, but total time is never going to be less than total space, when expressed in big-O notation
Post reply on HN