Timeline for Logarithmic vs double logarithmic time complexity
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 2, 2012 at 17:26 | comment | added | RBarryYoung | In the real world, a factor of 5 is pretty significant, and the number of items can often be 10^9 or even 10^12. | |
| Jul 19, 2012 at 11:21 | comment | added | A T | Note that there have been a bunch of improvements since VEB trees, amounting in data-structures on RAM with search/insert/delete complexity of $\mathcal{O}(log\ log\ n)$ without randomisation (deterministic) and $\mathcal{O}(\sqrt{log\ log\ n})$ with randomisation. See Deterministic Sorting in $\mathcal{O}(n\ log\ log\ n)$ Time and Linear Space. by Han, and $\mathcal{O}(\sqrt{log\ log\ n})$ Expected Time and Linear Space. by Han and Thorup. | |
| Apr 12, 2012 at 5:54 | history | edited | Raphael |
edited tags
|
|
| Mar 23, 2012 at 10:35 | vote | accept | Ghassen Hamrouni | ||
| Mar 23, 2012 at 10:35 | vote | accept | Ghassen Hamrouni | ||
| Mar 23, 2012 at 10:35 | |||||
| Mar 22, 2012 at 15:58 | comment | added | singhsumit | basically you should look at constants involved in the algorithm for smaller value/size of input. Ideally we would like them to be small. | |
| Mar 22, 2012 at 15:31 | answer | added | Raphael | timeline score: 10 | |
| Mar 22, 2012 at 15:27 | answer | added | Alex ten Brink | timeline score: 6 | |
| Mar 22, 2012 at 15:02 | answer | added | Dave Clarke | timeline score: 6 | |
| Mar 22, 2012 at 14:46 | history | edited | Raphael | CC BY-SA 3.0 |
deleted 18 characters in body
|
| Mar 22, 2012 at 14:23 | history | asked | Ghassen Hamrouni | CC BY-SA 3.0 |