<story><title>What does O(log n) mean, exactly?</title><url>http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly/2307314#2307314</url></story><parent_chain><item><author>Joeboy</author><text>I sometimes wonder, what sort of people actually need to know about Big-O notation? In about 15 years of working in IT I don&apos;t recall anybody ever using it in a work context. Generally something like &quot;this strategy will become very slow when we have a lot of users&quot; seems adequate. Admittedly I&apos;m only a humble web developer. Do you regularly talk in Big-O at work? What is your job?&lt;p&gt;Edit: Despite being only a humble web developer I understand that fast algorithms are better than slow ones. I&apos;m wondering how Big O &lt;i&gt;notation&lt;/i&gt; is used in the real world.</text></item></parent_chain><comment><author>0x0</author><text>Even a simple PHP script that needs to work with a large data set can quickly run into problems if you don&apos;t pay attention to algorithm complexity.&lt;p&gt;Consider this simple script that first creates a dataset of strings &quot;x0&quot;, &quot;x2&quot;, &quot;x4&quot;, &quot;x6&quot; etc. (500000 entries)&lt;p&gt;The task is to count from 0 to a 1000 to see whether the string &quot;x&quot;+NUMBER is present. Using a linear search with array_search() is super slow, but if you switch the storage from array values to array keys, and use a hash lookup via array_key_exists(), suddenly it flies:&lt;p&gt;% time php -dmemory_limit=512M -r &apos;$entries = array(); for($i=0;$i&amp;#60;1000000;$i+=2){ $entries[] = &quot;x&quot;.$i; };  $hits = 0; for ($i=0;$i&amp;#60;1000;$i++) { if(array_search(&quot;x&quot;.$i,$entries)!==false) $hits++; } var_dump($hits);&apos;
int(500)
php -dmemory_limit=512M -r   11.25s user 0.09s system 99% cpu 11.362 total&lt;p&gt;So, 11.362 seconds for a linear algorithm.&lt;p&gt;% time php -dmemory_limit=512M -r &apos;$entries = array(); for($i=0;$i&amp;#60;1000000;$i+=2){ $entries[&quot;x&quot;.$i]=true; };  $hits = 0; for ($i=0;$i&amp;#60;1000;$i++) { if(array_key_exists(&quot;x&quot;.$i,$entries)) $hits++; } var_dump($hits);&apos;
int(500)
php -dmemory_limit=512M -r   0.35s user 0.06s system 99% cpu 0.419 total&lt;p&gt;And 0.419 seconds for the hash one.&lt;p&gt;If you increase the workload to counting from 0 to 10000, it gets even worse in the linear case, while the hash key lookup finishes at about the same time as earlier!&lt;p&gt;% time php -dmemory_limit=512M -r &apos;$entries = array(); for($i=0;$i&amp;#60;1000000;$i+=2){ $entries[] = &quot;x&quot;.$i; };  $hits = 0; for ($i=0;$i&amp;#60;10000;$i++) { if(array_search(&quot;x&quot;.$i,$entries)!==false) $hits++; } var_dump($hits);&apos;
int(5000)
php -dmemory_limit=512M -r   115.96s user 0.29s system 99% cpu 1:56.52 total&lt;p&gt;So, 1 minute 56.52 seconds for a linear algorithm.&lt;p&gt;% time php -dmemory_limit=512M -r &apos;$entries = array(); for($i=0;$i&amp;#60;1000000;$i+=2){ $entries[&quot;x&quot;.$i]=true; };  $hits = 0; for ($i=0;$i&amp;#60;10000;$i++) { if(array_key_exists(&quot;x&quot;.$i,$entries)) $hits++; } var_dump($hits);&apos;
int(5000)
php -dmemory_limit=512M -r   0.37s user 0.06s system 99% cpu 0.440 total&lt;p&gt;And 0.440 seconds for the hash one.</text></comment>
<story><title>What does O(log n) mean, exactly?</title><url>http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly/2307314#2307314</url></story><parent_chain><item><author>Joeboy</author><text>I sometimes wonder, what sort of people actually need to know about Big-O notation? In about 15 years of working in IT I don&apos;t recall anybody ever using it in a work context. Generally something like &quot;this strategy will become very slow when we have a lot of users&quot; seems adequate. Admittedly I&apos;m only a humble web developer. Do you regularly talk in Big-O at work? What is your job?&lt;p&gt;Edit: Despite being only a humble web developer I understand that fast algorithms are better than slow ones. I&apos;m wondering how Big O &lt;i&gt;notation&lt;/i&gt; is used in the real world.</text></item></parent_chain><comment><author>benhoyt</author><text>Yes, regularly. I&apos;m a backend web developer who works on a fairly large-scale website, and program mostly in Python. It&apos;s pretty important to know that code like this (which we have in our photo search code):&lt;p&gt;&lt;pre&gt;&lt;code&gt;   for image in images:
       if image.hotel_id in hotel_ids:
           ...
&lt;/code&gt;&lt;/pre&gt;
will be O(N) if hotel_ids is a set or dict (with O(1) lookup), but O(N²) if hotel_ids is a list (with O(N) lookup). We&apos;re not talking about micro-optimizations here -- when N is of moderate size, it can mean the differences in render time between 30 milliseconds and 3 seconds.&lt;p&gt;When developers don&apos;t have a feel for this, it really slows them down -- both figuratively and literally.&lt;p&gt;FYI, I wrote a blog entry about how our photo search engine works here: &lt;a href=&quot;http://tech.oyster.com/how-our-photo-search-engine-really-works/&quot; rel=&quot;nofollow&quot;&gt;http://tech.oyster.com/how-our-photo-search-engine-really-wo...&lt;/a&gt;</text></comment>