interesting new container algorithm -- worth the interest?

Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.

AVL tree (for comparison):
Inserting in sorted order: O(logn)
Removing with sorted order: O(logn)
Finding: O(logn)
Iterating in sorted order: O(n)

My algorithm:
Inserting in sorted order: O(sqrt(n)), but with average time of logn
Removing with sorted order: O(1)
Finding: O(1)
Iterating in sorted order: O(n)

I think it's really cool, but the O(sqrt(n)) insertion worries me. It would only happen if it was fed something that was already sorted, which I think would be a common case.

- Evan Ovadia

Quote:

---

Originally Posted by Verdagon

Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.

AVL tree (for comparison):
Inserting in sorted order: O(logn)
Removing with sorted order: O(logn)
Finding: O(logn)
Iterating in sorted order: O(n)

My algorithm:
Inserting in sorted order: O(sqrt(n)), but with average time of logn
Removing with sorted order: O(1)
Finding: O(1)
Iterating in sorted order: O(n)

I think it's really cool, but the O(sqrt(n)) insertion worries me. It would only happen if it was fed something that was already sorted, which I think would be a common case.

- Evan Ovadia

---

I would like to see your proofs of those claims of O(1) for sorting and finding algorithms.

Quote:

---

Originally Posted by Verdagon

Hey guys, I just designed a new container algorithm (think stl::set) and I wanted to know if you all think it looks useful.

---

I noticed that you posted this in the C++ programming forum, though it is about a general data structure that could be implemented in and for any programming language. To check: you have implemented this in C++, presumably with an interface along the lines of std::set, and want to share it with us?

Quote:

---

Originally Posted by Verdagon

I think it's really cool, but the O(sqrt(n)) insertion worries me.

---

In other words, you cited O(sqrt(n)) as the worst case for insertion? If so, you are also citing O(1) search as the worst case? I agree with nimitzhunter: you really should elaborate.

Quote:

---

Originally Posted by nimitzhunter

I would like to see your proofs of those claims of O(1) for sorting and finding algorithms.

---

Assuming that the claimed properties are correct, you still need n log n time in the average case for sorting since you would be inserting n items with an average case of log n time to insert each item. O(1) for finding is already well known with hash tables, but that is in the average case with a good hash function, not the worst case (plus hash tables are not sorted).

I already know how to make a container with O(sqrt(n)) finding, insertion and removal, and O(n) iteration through them in order, and I bet your idea is very similar.

You have an array of items and an array of list indexes. The list indexes amount to a linked-list of the items in order, and the array contains the items in random order.
With insertion you swap a random item to the nth spot and put the new item where that item came from. You also update the list indexes to maintain the list in order.
With removal you do the swap with last and pop trick, whilst also updating the list indexes.
For searching you first step through the array over sqrt(n) items finding the lowest item that is lower than the desired item, and then you continue through the list from that point.
Basically the idea is the heart of the OrderSort algorithm, which is an O(n*sqrt(n)) sorting algorithm.
Memory usage is O(n).

Are you sure yours isn't the same thing and you've simply put the Big-Oh notations against the wrong things? Otherwise, care to explain how your claims are possible?

Note that what I've described is still comparison based. If yours is not comparison based (which I can't see how it could be given O(1) finding), then it isn't anywhere near as generic as a std::set.

I also know of an algorithm where insertion, find, and removal are O(1), although it assumes a limited range of values, and has something like O((n*k)!) setup time and memory requirements. You create enough arrays to contain every possible state and store a little extra info about which operation takes you to which other state.
My point being that you also need to state the memory usage.

I'm reluctant to post the code because I want to write one of those fancy academic papers first, so I can get credit before I release it. When it's written and released, I'll totally post it here first =D

Yes, it can be done in any language, I just wrote this one in C++.

This is distantly related to hash tables, so it has the same removing/finding properties as it. I thought hash tables were constant finding/removal, but you're right, hash tables do have a worst case O(n), huh? It's odd that so many places say its O(1) without mentioning collisions and stuff getting in the way.

n log n average time for sorting would be correct.

Very interesting reply, I've never heard of this kind of structure. What's it called?

My structure doesn't sound like what you've explained, but the space requirements for this would would be O(n).

Quote:

---

Inserting in sorted order: O(sqrt(n)), but with average time of logn
Removing with sorted order: O(1)
Finding: O(1)
Iterating in sorted order: O(n)
space requirements for this would would be O(n)

---

O_o

If by "finding" you mean indexing (i.e. getting the 27 element is O(C)) and by "with average time of logn" you mean "with amortized time of logn" I believe you.

Otherwise, pick three of the five and call it a day.

[Edit]
Oops.

Quote:

---

it has the same removing/finding properties as it

---

I missed this.

Considering what that would mean for your algorithmic complexities, I completely believe you.

[/Edit]

Soma

Quote:

---

What's it called?

---

iContainer of course!

Soma

Quote:

---

Originally Posted by Verdagon

I'm reluctant to post the code because I want to write one of those fancy academic papers first, so I can get credit before I release it. When it's written and released, I'll totally post it here first =D

---

Yes, but then... what's the purpose of this thread if we can't confirm your claims and you can detail them?

Best if we wait until you can produce the algorithm. I, for one, will be eagerly awaiting.

Okay cool. I was afraid the sqrt(n) insertion would mean that nobody would take it seriously because its slow, but apparently you guys do =D

I'll make that paper right away!

Quote:

---

Originally Posted by Verdagon

Okay cool. I was afraid the sqrt(n) insertion would mean that nobody would take it seriously because its slow, but apparently you guys do

---

Of course we do! You have to take into consideration structures like these are used in many contexts. For those in which insertion speed is not a variable to take into consideration (either because there's no insertion happening, or it happens in non performance critical areas), sqrt(n) insertion is a non issue.

Quote:

---

Originally Posted by Verdagon

Okay cool. I was afraid the sqrt(n) insertion would mean that nobody would take it seriously because its slow, but apparently you guys do =D

I'll make that paper right away!

---

It depends on what it's used for in my opinion. If insertion is a relatively rare solution, this container might still be better than others. But if insertion is more common this might be useless.

But I agree what has been set before: I doubt your claims, to be honest. See, an O(1) search implies quite a lot...


Edit: I just had a thought... Are those complexities not dependent on another variable, such as the length of the input. Eg. if we insert strings into it, is the complexity not dependent on the length? If they are, you should add them to the complexity notations. If not, then I doubt the O(1) search worst case a lot...

Quote:

---

Originally Posted by EVOEx

But I agree what has been set before: I doubt your claims, to be honest. See, an O(1) search implies quite a lot...

---

I may have misinterpreted the statement, but it seems to me that Verdagon admitted in post #5 that the worst case for search is actually O(n).

Quote:

---

Originally Posted by laserlight

I may have misinterpreted the statement, but it seems to me that Verdagon admitted in post #5 that the worst case for search is actually O(n).

---

Hmm that's not how I read that post. But if that is the case, wouldn't it make his container always slower than the AVL tree? I mean, it would only be faster if there would be a large number of removes, but for that you'd need the (slower) insert first.

If find is O(n), I don't see how remove can be O(1)