14 ms·

When Big O Fools You

• ctvo 10y ago
  If the author sees this: please consider changing your color choices. It'd make reading the content you put so much work into producing easier for everyone. I couldn't finish the post. The 90s hacker's lair colors were that offensive.
  • T0T0R0 10y ago
    The process of weeding out. Sometimes it's better to select against sensitive people.
    • tdb7893 10y ago
      Why would you select against people reading your article?
    • acbabis 10y ago
      Why would you select against people with poor vision?
      • k__ 10y ago
        The green seems a bit harsh, yes. But all in all it is a good page for people with poor vision. No low-contrast and no white background, which are both considered bad on screens.
        • acbabis 10y ago
          Yes, the white on black is fine. I checked the #8a7ae2 purple (http://webaim.org/resources/contrastchecker/ http://webaim.org/resources/contrastchecker/) and, surprisingly, it passes WCAG AAA guidelines. I say "surprisingly" because it hurts my eyes. I think jumping between the alternating white and purple is what does it.
      • T0T0R0 10y ago
        Why do you hate freedom?
    • tillytal 10y ago
      Why would you select against `; drop database prod;?
  • nutjob123 10y ago
    I agree. Its quite distracting. I didn't get through it.
  • johnloeber 10y ago
    Note that it's not so much the grey-on-black that's offensive, but the bright green and dark purple that produce eye strain. If you're going to use a black background, use light pastel colors for your fonts. That's usually a pretty good reading experience.
  • pc86 10y ago
    This is not what "offensive" means.
    • mistercow 10y ago
      It's a bit of an older usage than is common today, but it is correct. You'll also find this usage in phrases like "offensive odor".
    • TylerE 10y ago
      That's exactly what offensive means. adjective 1. causing resentful displeasure; highly irritating, angering, or annoying: offensive television commercials. 2. unpleasant or disagreeable to the sense: an offensive odor. 3. repugnant to the moral sense, good taste, or the like; insulting:
  • Afton 10y ago
    While I don't doubt that the author could fix this up, you are not helpless either. If you have colour/vision problems it is often worthwhile to install a client-reader bookmarklet or plugin to your browser, which may come along with a host of other benefits (like saving, place-marking, etc).
    • throwanem 10y ago
      Or a bookmarklet like this one: javascript:(function(){function%20R(w){try{var%20d=w.document,j,i,t,T,N,b,r=1,C;for(j=0;t=["object","embed","applet","iframe"][j];++j){T=d.getElementsByTagName(t);for(i=T.length-1;(i+1)&&(N=T[i]);--i)if(j!=3||!R((C=N.contentWindow)?C:N.contentDocument.defaultView)){b=d.createElement("div");b.style.width=N.width;%20b.style.height=N.height;b.innerHTML="<del>"+(j==3?"third-party%20"+t:t)+"</del>";N.parentNode.replaceChild(b,N);}}}catch(E){r=0}return%20r}R(self);var%20i,x;for(i=0;x=frames[i];++i)R(x)})();%20javascript:(function(){var%20newSS,%20styles='*%20{%20background:%20white%20!%20important;%20color:%20black%20!important%20}%20:link,%20:link%20*%20{%20color:%20#0000EE%20!important%20}%20:visited,%20:visited%20*%20{%20color:%20#551A8B%20!important%20}';%20if(document.createStyleSheet)%20{%20document.createStyleSheet("javascript:'"+styles+"'");%20}%20else%20{%20newSS=document.createElement('link');%20newSS.rel='stylesheet';%20newSS.href='data:text/css,'+escape(styles);%20document.getElementsByTagName("head")[0].appendChild(newSS);%20}%20})();%20javascript:(function(){var%20d=document;%20function%20K(N,w)%20{%20var%20nn%20=%20d.createElement(w),%20C%20=%20N.childNodes,%20i;%20for(i=C.length-1;i>=0;--i)%20nn.insertBefore(C[i],nn.childNodes[0]);%20N.parentNode.replaceChild(nn,N);%20}%20function%20Z(t,w)%20{%20var%20T%20=%20document.getElementsByTagName(t),%20j;%20for%20(j=T.length-1;j>=0;--j)%20K(T[j],w);%20}%20Z("blink",%20"span");%20Z("marquee",%20"div");%20})();%20javascript:(function(){var%20H=["mouseover","mouseout","unload","resize"],o=window.opera;%20if(document.addEventListener/*MOZ*/&&!o)%20for(j%20in%20H)document.addEventListener(H[j],function(e){e.stopPropagation();},true);%20else%20if(window.captureEvents/*NS4*/&&!o)%20{%20document.captureEvents(-1/*ALL*/);for(j%20in%20H)window["on"+H[j]]=null;}%20else/*IE*/%20{function%20R(N){var%20i,x;for(j%20in%20H)if(N["on"+H[j]]/*NOT%20TEXTNODE*/)N["on"+H[j]]=null;for(i=0;x=N.childNodes[i];++i)R(x);}R(document);}})();%20javascript:(function()%20{%20var%20c,%20tID,%20iID;%20tID%20=%20setTimeout(function(){},%200);%20for%20(c=1;%20c<1000%20&&%20c<=tID;%20++c)%20clearTimeout(tID%20-%20c);%20iID%20=%20setInterval(function(){},1000);%20for%20(c=0;%20c<1000%20&&%20c<=iID;%20++c)%20clearInterval(iID%20-%20c);%20})(); which strips out basically all the ill-considered design choices you're likely to find on a page, including best-of-1993 color palettes like that under discussion here. If you don't want to go that route, most modern browsers have a reader function built in, which extracts the page content and displays it with high contrast, a readable font, and no annoyances.
  • 01831810109 10y ago
    Yeah, every website needs to be plastered with big Fisher Price[tm] Facebook buttons and have unreadable hipster light-gray-on-white text.
    • k__ 10y ago
      True story. I don't know how long it will take us till we finally stop with the white backgrounds...
  • magic_beans 10y ago
    I absolutely agree, but not everyone is gifted with good taste. Try the Instapapr Text bookmarklet!
  • khedoros 10y ago
    I didn't find it offensive. The color scheme isn't that far off from what I prefer for my terminal settings. What would you have preferred the author do differently?
  • dingo_bat 10y ago
    I like the colors a lot. Much easier on the eyes than blinding white with gray text.
• Kenji 10y ago
  This is a great point and I'll probably have to do some performance measurements and change parts of my code now. I should be more careful with sacrificing contiguous storage for O(1) insertions. It is also worth noting that some manuals say that appending to an array list is O(1) amortized. Which is true, if you make an amortized analysis (which essentially distributes the workload of copying the array into a larger block over all the inserts). That's to keep in mind for systems that have to be realtime or at least produce stable framerates. The worst-case is important and amortized analysis generously glosses over it. EDIT: Not inserting, appending
  • ncw33 10y ago
    Insertion into an array list at a uniformly-distributed location is always O(n): you can't avoid moving half the list. Appending is amortized O(1).
    • rifung 10y ago
      Not the person you're responding to but perhaps that person meant assuming your insertions are uniformly distributed? Then I think insertion is O(n) amortized..? At an insertion you'd have (n + (n-1) + .. + 1)/n = O(n^2) / n = O(n) The first part comes from each possible run times, each with probability 1/n. You might have to expand the list but that'd also be O(n) amortized.
    • deleted 10y ago
      [deleted]
    • Kenji 10y ago
      You are right, my bad. I meant appending.
• ncw33 10y ago
  In no so many words, the article is pointing out that O(n) + O(1) is not necessarily quicker than O(n) + O(n): both add to O(n) (since only the highest-order factor matters), and the constant factor is unsurprisingly better for array lists. He's not benchmarking an O(1) operation against an O(n), or anything surprising, or even pointing out a "hidden" O(n) operation, it's simply a demonstration that O(n) + O(1) = O(n).
  • jandrese 10y ago
    Also, Big-O notation is a theoretical construct for thinking about complexity that works well for academic proofs but glosses over many real world considerations. Those ignored constant factors can be large and the datasets are not always large enough to amortize their cost.
    • valarauca1 10y ago
      Furthermore amortization isn't always accounted for in Big-O. Inserting into into the head of a linked list is O(1), and for a vector it is O(n). But on modern hardware vector inserts are much faster. If your software engineering begins and ends with Big-O notation, your likely doing a terrible job. Measure, and test. Always.
      • stcredzero 10y ago
        I would say, "If your software engineering begins and ends with [jargon] you're likely doing a terrible job. Measure, and test. Always." As a field, do we measure and test the effect of using various programming paradigms, patterns, and coding standards? I don't think most companies do this. Most developer decisions are made by "gut." As a field, we are still more like the "before" of Moneyball than the after.
        • _benedict 10y ago
          There's a third option: analysis and understanding. This seems to be entirely forgotten by the "measure, test" crowd - the scientific method requires a hypothesis to test for measurements to be meaningful, and separately not all things that are produced are "tested" in every aspect, since many things are well established, and the application of that existing theoretical framework makes measurement and testing a waste of time. Having a theoretical understanding of the thing you care about is far more important than the "measure, test" step - which is certainly important, but by itself of really limited power.
• sn41 10y ago
  I agree with the fundamental point in the article, but isn't it well known that when you consider multiple levels of the memory hierarchy as a whole, big O notation needs to be modified to take into account the relative cost of access? I think the problem is not so much the big-O notation, but that the underlying assumption that the data access is from an "all main memory" model with no cache or secondary storage is often forgotten. For example, in database algorithms, all memory operations are often considered to be unit cost since they are an order cheaper when compared to accessing the disk storage?
  • geophile 10y ago
    Big O notation is typically counting comparisons, and ignores constant factors. It isn't that memory hierarchy is ignored so much as the equating of comparison growth (in n) with performance. The field of cache oblivious algorithms is focused explicitly on memory hierarchy, and accounts for cache misses.
    • SamReidHughes 10y ago
      It's typically not counting comparisons, there are none when inserting elements. But sometimes it pretends that comparisons are O(1).
  • SamReidHughes 10y ago
    That depends on whether you expect the data to already be in memory or not. If it's already in memory, you would care a lot about cache locality. And in general, you don't want to spuriously lose on some benchmark if there's anything you can do about it.
• justusw 10y ago
  This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an ArrayList will be in O(1) given enough insert operations. Essentially, you over-allocate in order to save time. You're trading time complexity for space complexity. A really good explanation on amortised analysis can be found here on Wikipedia, which explicitly treats ArrayList: https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Array https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_Arr... As always, a look into the source code of your language of choice helps. In Python, a list object over-allocates using a very peculiar, but finely tuned formula: https://github.com/python/cpython/blob/09dc3ec1713c677f71ba7c536140ce12801a5036/Objects/listobject.c#L42 https://github.com/python/cpython/blob/09dc3ec1713c677f71ba7...
  • mezuzza 10y ago
    This point should be understood very clearly: The article isn't wrong that an ArrayList has O(n) for a single insertion. However, the article misses that amortized analysis shows that the same structure can be made to have O(n) for n insertions as well. In effect, ArrayLists can be thought to have O(1) insertion time in practice meaning that all you are comparing are the differences in constants between the two structures. I think the biggest takeaway from this isn't that big-O can fool you (which it very well can), but that misunderstanding analysis can lead to poor decisions. A better argument for big-O fooling you can be found using Quicksort and any proper O(n Log(n)) sorting algorithm. Quicksort will outperform most in practical cases, but is technically O(n^2) in the worst case (average case O(n Log(n)).
    • firethief 10y ago
      Isn't that an argument for average case performance being a better predictor of average cases than worst case performance?
      • 10y ago
• qwertyuiop924 10y ago
  Here's a question: How often does this matter? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating them for that reason only (assuming that there is any non-perf reason to stick with them) is a premature optimization. But if you ARE optimizing, yeah, you need to think about how often worst-case occurs. Because big O only tells you about worst-case. NOT the average.
  • cdavid 10y ago
    Memory contiguity may be the most fundamental thing to keep in mind when doing numerical computing, for example.
    • qwertyuiop924 10y ago
      Okay, so now I know.
  • SamReidHughes 10y ago
    Big O notation is used to describe whatever you want it to. The average case is the usual choice, in fact.
    • qwertyuiop924 10y ago
      Oh. Sorry.
  • timmytokyo 10y ago
    In game dev, it often matters a lot. The difference between code that takes cache performance into account and code that does not is often measured in frames per second.
  • corysama 10y ago
    A cache miss isn't noticeable by a human. Code that cache misses a lot runs 10-100x slower than code that takes into consideration that it's running on a physical machine and not an abstraction. That is very noticeable by humans. Even when your data structures and algos are designed with a nice O(logN), it's very noticeable when one program bogs down with 1/6 the data compared to another. I work in games, so the story I tell new kids is: The PlayStation2 ran at 300Mhz and a cache miss would cost you 50 cycles. The PlayStation3 ran at 3200Mhz and a cache miss would cost you 500 cycles. So, if you are cache missing a lot, your PS3 game will run as if it were on a PS2. In other words, not paying attention to cache make your computer run like it's 10 years older than it is. You paid for a modern machine, but you are getting the results of a Craigslist junker. This is true outside of games. It's the reason 4x2Ghz cellphones struggle to run seemingly simple apps. It's a big part of the reason people struggle to orchestrate armies of servers (distributed computing is easier when it's 90% less distributed). Is it really harder to work with the cache system instead of ignoring it? Yeah, it requires a tiny bit of study an a little bit of planning. In contrast, the theme I see a lot online is to completely dismiss physical reality in favor or theory. And, the theme I see almost universally in the students (and many senior engineers) I interview is complete ignorance of the very existence of cache and it's effects on the code they write. It's very concerning...
• stcredzero 10y ago
  Make Sure the Abstraction is Worth It Yes! All abstraction has a price. This is what people really mean when "all abstractions leak." Basically, all code and runtime features have a cost in terms of developer resources, cpu, memory, etc. The "inner game" of development isn't being able to muster huge amounts of "cleverness" power. The "inner game" is being able to put whatever resources you have to the best possible use.
  • johncolanduoni 10y ago
    This isn't true at all. What's the cost in developer resources, cpu, or memory of making a complex number class in C++ a template over floats and doubles? How about the cost of using Rust's generics to make a parser that can parse from any linear source of bytes (e.g. both files and in memory byte arrays)? There's plenty of abstractions which don't actually cost anything, and there's room for even more.
    • Retra 10y ago
      What's the cost in making a template more generic? Greater compile time. Need for compiler that can handle generics. Greater number of functions in binaries, and thus more unique places for bugs to occur. Dynamic library bloat. Harder to understand code. Quirky edge cases. Harder to learn languages. Harder to parse languages. And of course, developer time is spent dealing with all of this. Abstractions leak because they are models, and thus are necessarily different from the concrete things that they model. These differences can and will cause problems. Generic programming is an abstraction that pretends you aren't working on low-level un-typed system. And you pay for that abstraction any time you need to deal with low-level demands through that abstraction.
      • johncolanduoni 10y ago
        > Greater compile time. Not really with newer generics implementations (.NET, Rust, etc.). I don't think anyone thinks C++ templates are ideal, and the others show this at least a non-essential cost. > Greater number of functions in binaries, and thus more unique places for bugs to occur. Less human written code, so this reduces the surface area to the compiler; which is an "issue" no matter how low level your code is. > Dynamic library bloat. Your alternatives are A. duplicate the classes yourself B. let the compiler duplicate them. Where's the bloat? C++ requires you to explicitly instantiate templates if you want them in a library, and usually they're just left to the header. The others I listed won't generate anything unless you actually use a particular instantiation. > developer time is spent dealing with all of this It's pretty hard to argue that more developer time is wasted by the compiler writer than that of the time saved for developers who use the language for such a broadly used feature. > Abstractions leak because they are models, and thus are necessarily different from the concrete things that they model. What concrete thing do generics model? Tediously copy-pasted code? These will only be different if you mess up when you do the copy-pasting. > Generic programming is an abstraction that pretends you aren't working on low-level un-typed system. What? It's an abstraction over an already typed system that obviates the need to duplicate code, which after the generics are unwound produces the same code you would have had anyway. You're just as far or close to the low-level un-typed system as you were before. "All abstractions leak" is a nice platitude, but handwaving about "models" and "concreteness" doesn't prove anything.
• altendo 10y ago
  A lot of the focus in the HN comments is on ArrayLists, but I'm curious why the author chose to give linked lists an O(1) insert time. In some implementations (doubly linked list, inserting at the head of the list) I can see the O(1) time, but when appending to the end it also is O(n) because one has to traverse the entire list of elements before updating the link at the end of the list. Might just be nitpicking here but that might also be affecting the author's results.
  • tbirdz 10y ago
    Just keep a pointer to the head and tail of the list. You can then append to either end of the list in O(1). When you put a new node at the tail end, use the tail pointer to get to the tail node instead of walking the whole list. Of course, you need to make sure the head/tail pointers are always updated to point to the current head/tail of the list.
• CountHackulus 10y ago
  Big O isn't fooling you, it's giving you a one-function explanation of how the algorithm runs on an idealized system as the size of the problem increases. There's other systems you can simulate for big O, but the math is much harder and you wouldn't generally use it unless you're doing something complex like a cache-oblivious algorithm. If you're using solely big O to decide on an algorithm, you're fooling yourself. If performance is an issue, profile, benchmark, study, don't guess.
• billconan 10y ago
  I think the overemphasis of big O, especially during job interviews, is a sad thing. I think multi-threading is an equally important skill, that gets less attention.
  • SamReidHughes 10y ago
    It's not. The reason is, a lot of stuff isn't multithreaded or is just a bunch of threads talking to a database. (I've been asked questions about multithreaded stuff, in interviews at companies that specifically did multithreaded stuff. Companies that talked to databases would be better off asking SQL stuff.)
• lziest 10y ago
  Big O notation is asymptotic. Using only 5 insertions to understand Big O is definitely the wrong way. For example, insertion sort works better when the array is small, but insertion sort is definitely O(n^2), worse than qsort. Don't let Big O notation fool you, don't misunderstand Big O.
  • Guvante 10y ago
    Inserts in that chart is the ratio of inserts to reads. 5 means "write five times then read once per iteration" not "write five times".
• kazinator 10y ago
  The benefits of the list abstraction are small---because it's a clumsy, blub-like list abstraction with a container object and iterators. Look at the code; termination of the loop is even based on an integer count pulled from the container. A True Scotsman's linked list has no such thing. It's either an empty indicator (like NIL in Lisp) or a binary cell consisting of an item and a pointer to the next one. The benefit of that abstraction is that you can recurse over it directly without clumsy additional parameters having to be passed. Another benefit is substructure sharing. We can insert at the front of a list not only in O(1) time and that is great. But perhaps more importantly, existing copies of the list before the insertion do not change. And it is the same way if we delete from the front: we just move the local head pointer to the previous node, which doesn't affect anyone else who is still holding on to the pointer to the original front node. These lists also allow lock-free operation, unlike "heavy weight" containers. Suppose we have a list that acts purely as a container, but is shared by multiple threads. We can insert into it by consing a new node onto the head of the current snapshot of the list, and then doing an atomic-compare-swap to install that head in place of the old head. If it fails, it means the list changed behind our back; we cons the node onto the new list (or rewrite the cons to point to the new one as its "rest" pointer) and try again. Some of the caching benefits of the array will disappear if the array holds only references/pointers to items. In this example, the containers are typed. The List<int> actually can allocate the int objects in an array that packs them together in memory. Whereas the LinkedList<int> has individual separately allocated nodes which hold the int. Suppose the List and LinkedList hold pointers to heaped objects. Then the impact of caching is softened. It's still the case that multiple pointers in the array can be cached together; but these have to be traversed to access the items themselves. In the case of the LinkedList, we have to traverse a pointer to get to the next node and traverse a pointer to get to the heaped object. But two pointer traversals versus one is not as bad as one traversal versus zero. If the objects being traversed are fairly complex, and have pointers to additional objects that have to be examined during the traversal, it matters even less what kind of list they are accessed from. If I have a list of File objects, for each of which a stream is opened and a regex scan performed, why would I care whether it's an array list or a linked list. The results shown in this test case tell me that the performances of the two containers are not that far off! Here they are subject to a test case that is designed to highlight the difference between them by making the container content, and its processing, almost as trivial as possible. That 38 seconds versus 51 difference is almost purely in the container-related operations. That is as bad as it gets: from there, the more actual real work you do per container node, the smaller the actual difference. (What is 51 versus 38 in "orders of magnitude"? Why 0.12 orders. It's 0.42 "binary orders of magnitude" (where 1 binary order is a doubling; terminology mine). So in terms of classic Moore's Law (speed doubling every 18 months), that's a 7.6 month advance. "My arrays are 7.6 months ahead of your linked list container, in Moore's Law, in a pure benchmark; eat my dust!"
• AStellersSeaCow 10y ago
  There's a simpler and broader point: don't use Big O as the sole means of analysis of a high level language's data structures. The theoretical time/space complexity of a data structure may or may not accurately reflect how it's actually implemented in that language.
• Const-me 10y ago
  Ported to C++, added two ATL collections, also added 100M elements data point: https://github.com/Const-me/CollectionMicrobench https://github.com/Const-me/CollectionMicrobench Arrays are still generally faster than lists. The funny thing is Microsoft’s linked lists are faster than C++ standard vectors.
  • ric129 10y ago
    >The funny thing is Microsoft’s linked lists are faster than C++ standard vectors. If I had to guess, it's because the std::vector is more conservative in memory use and it causes more malloc/array copy calls.
    • Const-me 10y ago
      I think the main reason is CAtlList class encapsulates its own memory pool. It allocates RAM in batches. The default batch size for CAtlList is 10 elements/batch, user-adjustable in constructor, but I kept the default value 10. The elements are created directly adjacent to each other. This makes iteration faster because RAM locality despite the pointer-based data structure.
• jontro 10y ago
  I just read this nice piece on linked lists and why they have almost no place in programming nowadays http://cglab.ca/~abeinges/blah/too-many-lists/book/ http://cglab.ca/~abeinges/blah/too-many-lists/book/
• readams 10y ago
  A cache miss can be a slowdown of ~200x on modern CPU architectures. Lets say you have a choice of a O(n) algorithm that always misses the cache and a O(n lg n) algorithm that never misses the cache. The crossover point where it makes sense to use the O(n) algorithm will occur when: 200 * n = n lg n which occurs for n > 2^200. Most of us are not dealing with problems larger than can be represented in our universe, so cache efficiency matters, kids. Note that this changes for other comparisons. Going from n maximally cache inefficient vs n^2 cache efficient is only worth it for n up to 200, and n lg n --> n^2 up to n about 2223. Of course, in practice your algorithm won't be missing the cache on every access, so reality is somewhere between these values.
• caf 10y ago
  The result is that when you iterate over contiguous memory, you can access it about as fast as the CPU can operate, because you will be streaming chunks of data into the L1 cache. This is not true at all. You'll be able to access it about as fast as the memory can operate - it'll still be much faster than randomly chasing pointers all over the place - but the maximum processing speed of the CPU is an order of magnitude greater than that again.
• Rhapso 10y ago
  The question I always ask before replacing an n^2 process with an nlg(n) one is "Am I in that window where n^2 is actually faster?"
• jwatte 10y ago
  One thing I didn't see in the article: in addition to cache misses, the list stores 3 words per word; the array between 1 and 2 (up to 3 only when reallocating,) so array touches less RAM, even when inserting.
• nayuki 10y ago
  Arrays are fast for getting random elements and inserting/deleting at the end (amortized), but slow for inserting/deleting in the middle. Linked lists are fast for inserting/deleting/getting at the beginning and end, but slow for random access for anything in the middle. So far, that's what the article covered. Now if you want fast random insertions/deletions and fast random access, this is possible with balanced trees. A tree-based list can support all single-element operations in O(log n) time. Sample code: https://www.nayuki.io/page/avl-tree-list https://www.nayuki.io/page/avl-tree-list
  • edejong 10y ago
    That's not what the article is about nayuki. The author of the article makes and proves a claim that arrays are faster than linked lists regardless of the insertion point. The metrics presented clearly show this. The reason for this abnormality is cache locality (there are other reasons, which I will not go into right here). Balanced trees can be pretty slow in fact. After some operations, a tree structure can become quite fragmented in memory, leading to many cache misses. In my experience, it is often faster to work with arrays instead of trees when processing in memory. However, using external storage, a b-tree often introduces quite some performance gain.
• happytrails 10y ago
  Oprah fooled me once!
• yandrypozo 10y ago
  The author is doing less than 10 insertions per benchmark, that's practically a constant O(1), even if you have to copy the entire array 5 or 10 times don't affect the Big O analysis
  • Moto7451 10y ago
    But he's inserting at the front of an array, which requires the rest of the elements to be copied into a new array. DotNetPerls has a clearer example: http://www.dotnetperls.com/list-insert http://www.dotnetperls.com/list-insert
• akandiah 10y ago
  Technically speaking, he ought to be using Big Theta (Θ) to describe his bounds. Throwing Big O around to describe everything is foolish.