A T
  • Member for 9 years, 9 months
  • Last seen more than a month ago
Data structure with search, insert and delete in amortised time $O(1)$?
Accepted answer
6 votes

Looks like the $\Omega(\dfrac{\log n}{\log\log n})$ barrier has been overcome by modifying the analysis from the chronogram technique. The new [lower] $\Omega(\log n)$ bound has been proved for ...

View answer
For what kind of data are hash table operations O(1)?
5 votes

Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees Firstly, we give the first ...

View answer
Set Similarity - Calculate Jaccard index without quadratic complexity
4 votes

An option would be to use the Signature Scheme of [1], size-based filtering: a scheme which uses size information to reduce the number of set pairs that need to be considered. They also experiment ...

View answer
Does there exist a priority queue with $O(1)$ extracts?
3 votes

Okay, finally got you the complexity you were looking for, and what's best, I found it in the literature: Worst-Case Complexity Delete: $\bf\mathcal{O}(1)$ Delete-min: $\bf\mathcal{O}(1)$ Find-min:...

View answer
Most efficient known priority queue for inserts
3 votes

Worst-case complexity Insert: $\mathcal{O}(1)$ Find-min: $\mathcal{O}(1)$ Decrease-key: $\mathcal{O}(1)$ Delete: $\mathcal{O}(\log \log n)$ Space: $\mathcal{O}(n)$ Proof THEOREM 1. We can implement a ...

View answer
Does there exist a priority queue with $O(1)$ extracts?
2 votes

Approaching this problem by maintaining two data-structures: an Array and a Binary Tree. To maintain indexing in the array, previously you'd have the $\Omega(\dfrac{\log n}{\log\log n})$ bound; but ...

View answer
Can every algorithm's running time be expressed as $\Theta(f(n))$?
1 votes

As a simple proof-by-contradiction take a look at any algorithm who's complexity depends on more than one variable, e.g.: $\mathcal{O}(nk)$. In such a case it is rarely possible to express running ...

View answer
Priority queue with unique elements and sublinear time merge?
0 votes

How about using a Strict Fibonacci Heap? - Here are the worst-case complexities: $$\mathcal{O}(1) \text{ find-min}$$ $$\mathcal{O}(\log_2 n) \text{ delete-min}$$ $$\mathcal{O}(1) \text{ insert}$$ ...

View answer
Most efficient known priority queue for inserts
0 votes

Worst-case complexity $\mathcal{O}(log\ M)$ insert, search, delete [see 'Lemma 3.1'] $\dagger\ \mathcal{O}(1)$ findMin, findMax, extractMin, extractMax, predecessor, successor $2M + \mathcal{O}(log\ M)...

View answer
Most efficient known priority queue for inserts
0 votes

Finally a simplification of the Brodal queue[1] has been released[2], which unlike[3]; are worst-case values (rather than amortised). Insert: $\mathcal{O}(1)$ Find-min: $\mathcal{O}(1)$ Decrease: $\...

View answer
Most efficient known priority queue for inserts
-1 votes

Worst-case complexity $\boldsymbol{\mathcal{O}(1)}$ insertion $\boldsymbol{\mathcal{O}(log\ \textbf{min}\{w_x, q_x\})}$ get-min, extract-min, delete, and decrease of an element $\boldsymbol{x}$ Where ...

View answer
Does there exist a priority queue with $O(1)$ extracts?
-2 votes

Analysis Insert: $\mathcal{o}(n\ log\ log\ n)$ Search: $\mathcal{o}(log\ log\ n)$ Delete: $\mathcal{O}(1)$ Space: $\mathcal{O}(n)$ Get-Min: $\mathcal{O}(1)$ Extract-Min: $\mathcal{O}(1)$ ...

View answer
Does there exist a priority queue with $O(1)$ extracts?
-2 votes

Find-min in $O(1)$ with expected update time of $O(\sqrt{log\text{ }log\text{ }n})$ See the 2007 paper: Equivalence between priority queues and sorting by Mikkel Thorup. Note: He refers to the 2002 ...

View answer
An efficient data structure supporting Insert, Delete, and MostFrequent
-3 votes

Worst-case complexity Insert: $\mathcal{O}(1)$ Find-min: $\mathcal{O}(1)$ Decrease-key: $\mathcal{O}(1)$ Delete: $\mathcal{O}(\log \log n)$ Space: $\mathcal{O}(n)$ Proof THEOREM 1. We can implement a ...

View answer