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

41–46 of 46 posts

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

#41

Post by nneonneo »

asboans wrote: post #36
consp wrote: post #18

Earlier quoted context omitted.

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

And any operation that takes n bits as input can be trivially turned into an O(1) time and O(2^n) space algorithm through tabulation.

Assuming you ignore or amortize the time necessary to create the table in the first place, of course.

This is the basis for rainbow tables: precomputed tables for mapping hashes to passwords, with a space-saving “hash chaining” trick to effect a constant factor reduction in table size. Such tables are the reason why passwords must be hashed with a unique salt when stored in a database.

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

#42

Post by aleksiy123 »

nneonneo wrote: post #40
aleksiy123 wrote: post #38

Earlier quoted context omitted.

The confusion is around space complexity vs auxiliary space complexity (extra space). space complexity is O(n) but auxiliary space complexity uses Theta for notation instead. But people aren't too picky on the notation and usually say something like "O(1) extra space" instead of using theta. https://en.m.wikipedia.org/wiki/Space_complexity

That’s not quite accurate. Big O notation and Theta notation are different ways of expressing the growth rates of functions - the choice of using Big O or Theta is independent of whether you’re trying to specify total space complexity or auxiliary space complexity. Saying something is O(n) tells you it grows at most linearly, but this would also admit e.g. log n. Saying something is Theta(n) tells you it grows exactl…

Yeah, you are correct I misinterpreted the article.

But yeah I guess space complexity vs auxiliary space complexity is just a bit ambigous.

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

#43

Post by Neywiny »

I had something like this. I was making a script that would parse a standardized file describing a molecule and create the atoms and bonds and whatnots. I found out that they time an object is added it iterates through all the objects to update them of the addition. This was very noticable even around 1k objects. I later grouped all the duplicated objects (such as all the oxygens) into 1 discontinuous object, leading to O(1 [the bonds] + #elements) instead of O(#bonds * #atoms).

In the end I still lost out to another package that did the same function a lot faster. May be interesting to look back to see how they did it.

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

#44

Post by ajuc »

yxhuvud wrote: post #31
xigoi wrote: post #24

Earlier quoted context omitted.

Why couldn’t it?

Because it takes n time to access n units of memory. Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead as that is usually what actually matters.

Let's say you have a lookup table and your algorithm looks up a value and returns it. O(n) space O(1) in time.

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

#45

Post by yxhuvud »

ajuc wrote: post #44
yxhuvud wrote: post #31

Earlier quoted context omitted.

Because it takes n time to access n units of memory. Heavily simplified due to caches etc. To the point where people sometimes measure in cache misses instead as that is usually what actually matters.

Let's say you have a lookup table and your algorithm looks up a value and returns it. O(n) space O(1) in time.

n is some value depending on the size of the input, so if you have a look up table that is O(n), then that memory needs to be initialized somehow. If you have a fixed size lookup table then it is O(1), even if it is big.

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

#46

Post by ajuc »

yxhuvud wrote: post #45
ajuc wrote: post #44

Earlier quoted context omitted.

Let's say you have a lookup table and your algorithm looks up a value and returns it. O(n) space O(1) in time.

n is some value depending on the size of the input, so if you have a look up table that is O(n), then that memory needs to be initialized somehow. If you have a fixed size lookup table then it is O(1), even if it is big.

Compile time fill a lookup table. Run time read 1 value from it. I call it O(1) in time, O(n) in memory. You call it O(1) in both, right?

Now move the compile time code to runtime.

I call it O(n) in time and memory. What do you call it?

If your say O(n) in time and memory - why is moving the code changing its complexity?

If you say still O(1) - then everything is O(1), thus proving P=NP among other things :)

Either way your interpretation isn't very useful.

Post reply on HN