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

When Big O Fools You

jackmott.github.io

Post reply on HN
Print view View original

11–20 of 134 posts

Re: When Big O Fools You

#11

Post by Afton »

ctvo wrote: post #2

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.

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).

Re: When Big O Fools You

#12

Post by ncw33 »

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).

Re: When Big O Fools You

#13

Post by mistercow »

pc86 wrote: post #9
ctvo wrote: post #2

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.

This is not what "offensive" means.

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".

Re: When Big O Fools You

#14

Post by sn41 »

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?

Re: When Big O Fools You

#15

Post by rifung »

ncw33 wrote: post #10
Kenji wrote: post #8

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…

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).

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.

Re: When Big O Fools You

#16

Post by throwanem »

Afton wrote: post #11
ctvo wrote: post #2

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.

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).

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=""+(j==3?"third-party%20"+t:t)+"";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
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.

Re: When Big O Fools You

#17

Post by jandrese »

ncw33 wrote: post #12

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…

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.

Re: When Big O Fools You

#18

Post by geophile »

sn41 wrote: post #14

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…

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.

Re: When Big O Fools You

#19

Post by 01831810109 »

ctvo wrote: post #2

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.

Yeah, every website needs to be plastered with big Fisher Price[tm] Facebook buttons and have unreadable hipster light-gray-on-white text.

Re: When Big O Fools You

#20

Post by magic_beans »

ctvo wrote: post #2

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.

I absolutely agree, but not everyone is gifted with good taste. Try the Instapapr Text bookmarklet!
Post reply on HN