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

An interesting data structure with search time O(sqrt n)

forum.dlang.org

Post reply on HN
Print view View original

61–70 of 76 posts

Re: An interesting data structure with search time O(sqrt n)

#61

Post by thaumasiotes »

rntz wrote: post #14
chias wrote: post #12

Isn't O(log(n)) equivalent to O(sqrt(n))?

No. Just as (e^n) grows faster (in the limit) than any polynomial of n, such as n^2 or n^100; likewise, log(n) grows slower than any polynomial of n, such as sqrt(n) = n^(1/2), or even n^(1/100). They are both practically pretty slow-growing, though. It may well be that for practical sizes, constant factors matter more than the asymptotic difference on present computers.

Well, you can get sqrt to nontrivial sizes pretty easily, where you can basically never grow log to nontrivial sizes. Looking at 100 million, the square root is ten thousand and the base-2 log is 26.5. The base-2 log of a googol is 332 (and, just for fun, the square root is 100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000).

But I actually wanted to respond to this:

> log(n) grows slower than any polynomial of n, such as sqrt(n) = n^(1/2)

It's correct to say that log(n) grows slower than any positive exponent of n, but what you've said is wrong in two ways:

- f(n) = n^(1/2) is not a polynomial, as a polynomial in n can only feature nonnegative integer exponents of n.

- f(n) = 300 is a polynomial in n, but it grows more slowly than log(n). (It's also larger, for any plausible value of n at all. So constant factors do matter, but the difference between log(n) and sqrt(n) is quite noticeable.)

Re: An interesting data structure with search time O(sqrt n)

#62

Post by Veedrac »

Veedrac wrote: post #60

Another thing that works is a length-sqrt(n) list of length-sqrt(n) sorted lists with internal gaps, like with Python's SortedContainers[1]. Something like this with a contiguous allocation would probably require quite a lot of empty space - 100% reserve for each subarray by necessity[2] and 50% for the array as a whole, so 200% overhead at worst and probably 90% overhead on average. Alternatively you can heap alloca…

After some thought, you can avoid so much reserve by just not having any reserve buckets (and thus no need for the header either). You can only resize once every O(sqrt n) operations and a resize costs O(n), so it's amortized O(n / sqrt n) = O(sqrt n) insertion. You can lower the constant factors a bit by doing occasional local reshuffling.

Not sure if it's a great idea, but it's tempting.

Re: An interesting data structure with search time O(sqrt n)

#64

Post by nikic »

mtdewcmu wrote: post #50
nikic wrote: post #13

Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Perform linear search in heap. Worst cast complexity O(n^(1/3) + n^(2/3)) = O(n^(2/3)). Insertion of an element. Find the last heap those maximum element is still larger than the element. Extract top element of the he…

Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.

That's true, I got confused with min and max there. gre's suggestion of using a min-max heap (if deletion is required) seems a reasonable workaround for this issue.

Re: An interesting data structure with search time O(sqrt n)

#65

Post by skj »

Veedrac wrote: post #59
hvidgaard wrote: post #58

Earlier quoted context omitted.

And BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.

Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.

I believe your and abcdabcd987's use of the term BST is not exactly what is commonly used. A BST refers to both the data structure and the algorithm used to manage it. An RB tree is a different concept. An RB tree is a binary tree, certainly, since the term "binary tree" implies no algorithms, but it is not a "binary search tree" in its specific denotation.

Re: An interesting data structure with search time O(sqrt n)

#66

Post by Veedrac »

skj wrote: post #65
Veedrac wrote: post #59

Earlier quoted context omitted.

Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.

I believe your and abcdabcd987's use of the term BST is not exactly what is commonly used. A BST refers to both the data structure and the algorithm used to manage it. An RB tree is a different concept. An RB tree is a binary tree, certainly, since the term "binary tree" implies no algorithms, but it is not a "binary search tree" in its specific denotation.

https://en.wikipedia.org/wiki/Binary_search_tree#Types

> There are many types of binary search trees. AVL trees and red-black trees are both forms of self-balancing binary search trees.

Re: An interesting data structure with search time O(sqrt n)

#67

Post by mtdewcmu »

nikic wrote: post #64
mtdewcmu wrote: post #50

Earlier quoted context omitted.

Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.

That's true, I got confused with min and max there. gre's suggestion of using a min-max heap (if deletion is required) seems a reasonable workaround for this issue.

Using min-max heaps should be workable; indeed, the resulting data structure seems to be a special case of the data structure described in section 3 of [1].

[1] http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/...

Re: An interesting data structure with search time O(sqrt n)

#68

Post by hvidgaard »

Veedrac wrote: post #59
hvidgaard wrote: post #58

Earlier quoted context omitted.

And BSTs can have O(n) lookup. The only property of a BST is that you know something about the value of the children compared to the parent. This means that a sorted linked list is a BST.

Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.

Terminology is important. A BST is what I defined. A balanced BST has an extra property, but you don't get to call a balanced BST just a BST, it only adds to confusion and unclear communication.

Re: An interesting data structure with search time O(sqrt n)

#69

Post by Veedrac »

hvidgaard wrote: post #68
Veedrac wrote: post #59

Earlier quoted context omitted.

Sure, but abcdabcd987 was evidently not suggesting using a completely general BST. That there exists a BST with the mentioned properties is sufficient to validate the claim made; that there exists a BST which does not is irrelevant.

Terminology is important. A BST is what I defined. A balanced BST has an extra property, but you don't get to call a balanced BST just a BST, it only adds to confusion and unclear communication.

I don't agree with your use of terminology; to me "BST" is just as much a class of things as "mammal" is. I will agree though that it has added confusion.

Re: An interesting data structure with search time O(sqrt n)

#70

Post by hvidgaard »

Veedrac wrote: post #69
hvidgaard wrote: post #68

Earlier quoted context omitted.

Terminology is important. A BST is what I defined. A balanced BST has an extra property, but you don't get to call a balanced BST just a BST, it only adds to confusion and unclear communication.

I don't agree with your use of terminology; to me "BST" is just as much a class of things as "mammal" is. I will agree though that it has added confusion.

> I don't agree with your use of terminology

When you say BST the only thing you've said is that it's a binary tree structure with a property about the childrens value compared to the parent. While saying that there is certain BSTs with O(lg_2 n) searches is true, there also exists BSTs with O(n) searches.

The original claim was that:

> BTW, why not BST, for everything is O(log n)?

Which is not true. A sorted linked list is the canonical counter example. There is no confusion of terminology, it is clearly defined in algorithmic literature on search trees.

Post reply on HN