Sunday, March 13, 2011

The simple Big-O Notation Post.

I make no claim to be a "computer scientist" or a software "engineer", those titles alone can spark some debate, I regard myself as a software developer and I generally don't study the math and science behind everything I do. I generally learn what is relevant and useful to my day to day functioning and only rarely go deeper and dabble in the theory behind it. This is one of those occasions, so I decided to scour the internet and see what I could pick up. I hope to keep this simple, practical and to the point.


Big-O:
  • Describes how the algorithm scales and performs, in terms of either the execution time required or the space used.
  • Is relative representation of complexity. This allows you to reduce an algorithm to a variable which in turn allows you to easily compare it to another.
  • Describes an upper limit on the growth of a function, in the other words the "worst case scenario".

There is also Big-Omega notation which looks at the lower bound  / "best case scenario" stating that the algorithm will take at least X amount of time and Big-Theta which is tight bound to both lower and upper / "average".

Some quick observations in determining Big-O:
  • A Sequence of statements, or things like conditional checks are constant: O(1)
  • A loop of statements result in : O(n) n being the number of loop executions.
  • Nested loops are multiplied together: O(n2) where n is the times the outer loop executes and m is the times the inner loop executes.

Comparing the common notation examples:
(Thanks to Algorithms: Big-Oh Notation.)
 

nConstant 
O(1)
Logarithmic
O(log n)
Linear
 O(n)
Linear Logarithmic
O(n log n)
Quadractic
O(n2)
Cubic
O(n3)
1111111
2112248
412481664
81382464512
161416642564,096
1,0241101,02410,2401,048,5761,073,741,824
1,048,5761201,048,57620,971,52010121016


Java code example:
Show examples of notations in the table above. 



Common Data Structures and Relative functions: Lists and Sets:
Structuregetaddremovecontains
ArrayListO(1)O(1)*O(n)O(n)
LinkedListO(n)O(1)O(1)O(n)
HashSetO(1)O(1)O(1)O(1)
LinkedHashSetO(1)O(1)O(1)O(1)
TreeSetO(log n)O(log n)O(log n)O(log n)
* ArrayList Notes:

Thanks to reader comments, the add method on an ArrayList should be: O(1) amortized (and O(n) in worse case). Useful reference links:

Constant Amortized Time

Linked List vs ArrayList

Maps:

StructuregetputremovecontainsKey
HashMapO(1)O(1)O(1)O(1)
LinkedHashMapO(1)O(1)O(1)O(1)
TreeMapO(log n)O(log n)O(log n)O(log n)
References:

Algorithms: Big-Oh Notation.

Algorithmic Complexity and Big-O Notation.

Determining Big O Notation An easier way .

Wikipedia.

84 comments:

  1. Hi,
    thanks for the post. It was nice to realize that I remember at least something from my CS course :).

    <nit-picker>
    I have an observation to some values in the last 2 tables though.

    It is not 100% true to say that add to ArrayList is O(1). In case underlying arrays requires extension, it will take O(n), where n is the number of elements already present in the array.

    As for the maps, O(1) is the case only in approximation. In fact, it's a bit more complex and depends on load factor, hash function distribution and length of the chain per hash value.
    </nit-picker>

    On the other side, one of key words in post title is "simple", so these comments are really some nerdy stuff :).

    ReplyDelete
  2. Thanks for the comments and from what i read, you're right.

    but

    :) yeah I tried to keep it simple, practical and easy to remember, so wanna stay away from the painfully technical details

    ReplyDelete
  3. You might want to star the ArrayList entry for 'add', and point out the following: add is O(1) amortized, but O(n) worst-case since the array must be resized and copied.

    See
    http://download.oracle.com/javase/6/docs/api/java/util/ArrayList.html
    http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist
    http://stackoverflow.com/questions/200384/constant-amortized-time

    ReplyDelete
  4. Thanks for the input Philip. Yeah, I'll make mention and add the links you mentioned, very helpful.

    ReplyDelete
  5. Great post mate,one of the best I have read on BigONotation. beauty of this post is simple, clean and concise and relavant example from Java and Collections make it more useful. I would recommend for any Java developer to read this post to get a clear Idea of BigO and that will certainly help them to analyze there Algorithm as well. hope to see some more article from you.

    Thanks
    Javin
    Why wait() and notify() method must be called from synchronized context

    ReplyDelete
  6. Very nice post. The cleanest I've ever seen so far.
    Thanks.

    Alin

    ReplyDelete
  7. Nice summary. While many implementations like to capture the theory of big-O; the associated cost of O(1) is often ignored.

    The big-O really depends on the parameters passed to the method/function. For example, if you're dealing with the actual data points it is incorrect to say that any of the LinkedList's operations are O(1). Since given the data, a search to find the list entries is still required.

    Have you given thought to the run-time resource usage to get the 'most optimal' performance?

    I previously leveraged ArrayList--almost exclusively--due to perceived smaller size and 'constant' access times. I have since retreated from the white rabbit, absent any wounds. The default ArrayList sizes clash with resizing of arrays that kill both performance _and_ resource usage.

    ReplyDelete
  8. There's one part that is either wrong, or I am crazy.
    while (startIndex < endIndex) {
    int midIndex = (endIndex - startIndex / 2) + startIndex;
    int midValue = data[midIndex];
    The formula for retrieving the midIndex is the problem. The parenthesis don't actually do anything in this case, the equation will be solved the same without it. Did you mean to write this: int midIndex = (endIndex - startIndex)/2 + startIndex ??
    Either way I found this post extremely helpful, I've had trouble finding easy to understand documentation on Big ) notation.

    ReplyDelete
  9. Well written, it was extremely helpful and easy to understand.

    ReplyDelete
  10. Thanks, nice and clearly explained. Another good one on Big O:

    Big O Notation

    ReplyDelete
  11. Great article, thank you!
    One question:
    You wrote: "Nested loops are multiplied together: O(n2) where n is the times the outer loop executes and m is the times the inner loop executes."
    Shouldn't it be: "Nested loops are multiplied together: O(n * m) where n is the times the outer loop executes and m is the times the inner loop executes."?

    ReplyDelete
  12. The issue comes, on the off chance that they just keep a reinforcement on the server. ExcelR Data Science Courses

    ReplyDelete
  13. Get your favourite garden sheds and all the household items in Auckland Newzealand on a single click. We provide you quality products and Bed with mattress nz lowest price..!

    ReplyDelete
  14. watch your favourite pinoy tambayan replays online in hd. All the pinoy channels and all the replays you will be watch online in hd.

    ReplyDelete
  15. Thanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post with people.
    remote developer jobs

    ReplyDelete
  16. watch all your favourite teleserye shows online on Pinoy Channel Tv free episodes in Single click full pinoy tv replays

    ReplyDelete
  17. I was reading your article and wondered if you had considered creating an ebook on this subject.Your writing would sell it fast.You have a lot of writing talent. bigo live diamond

    ReplyDelete

  18. Get all the latest clicksud online seriale online of clicksud and all the seriale online daily on this blog.

    ReplyDelete
  19. I admire this article for the well-researched content and excellent wording. I got so involved in this material that I couldn’t stop reading. I am impressed with your work and skill. Thank you so much. Tableau Data Blending

    ReplyDelete
  20. Great Content, If you wish to upskill yourself in the latest Technologies Do visit GoLogica Trainings

    ReplyDelete
  21. This comment has been removed by the author.

    ReplyDelete
  22. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article.
    data science course in indore

    ReplyDelete
  23. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article.
    data science course in coimbatore

    ReplyDelete
  24. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    data science course in gurgaon

    ReplyDelete
  25. I really enjoy simply reading all of your weblogs. Simply wanted to inform you that you have people like me who appreciate your work. Definitely a great post. Hats off to you! The information that you have provided is very helpful.
    data science course in bhilai

    ReplyDelete
  26. I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
    data science course in nagpur

    ReplyDelete
  27. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.data science course in jaipur

    ReplyDelete
  28. This comment has been removed by the author.

    ReplyDelete
  29. I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
    data science course in nagpur

    ReplyDelete
  30. I finally found great post here.I will get back here. I just added your blog to my bookmark sites. thanks.Quality posts is the crucial to invite the visitors to visit the web page, that's what this web page is providing.
    data science course in lucknow

    ReplyDelete
  31. I am really enjoying reading your well written articles. It looks like you spend a lot of effort and time on your blog. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work.
    data science course in kanpur

    ReplyDelete
  32. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article.
    data science training in navi mumbai

    ReplyDelete
  33. I just got to this amazing site not long ago. I was actually captured with the piece of resources you have got here. Big thumbs up for making such wonderful blog page!
    data science course in kochi

    ReplyDelete
  34. Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
    data science course in pune

    ReplyDelete
  35. Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
    Data Science Institute in Bangalore

    ReplyDelete
  36. I have to search sites with relevant information ,This is a
    wonderful blog,These type of blog keeps the users interest in
    the website, i am impressed. thank you.
    Data Science Course in Bangalore

    ReplyDelete
  37. I feel really happy to have seen your webpage and look forward to so many more entertaining times reading here. Thanks once more for all the details.
    Business Analytics Training in Hyderabad | Artificial Intelligence Course in Hyderabad | Business Analytics Course in Hyderabad

    ReplyDelete
  38. Very informative post! Here is a lot of information that can help any business start a successful social media campaign!

    Data Science Course

    ReplyDelete
  39. I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
    Data Analytics Course in Pune
    Data Analytics Training in Pune

    ReplyDelete
  40. I am impressed by the information that you have on this blog. It shows how well you understand this subject.
    Business Analytics Course in Pune
    Business Analytics Training in Pune

    ReplyDelete
  41. I want to say thanks to you. I have bookmark your site for future updates.
    data science course

    ReplyDelete
  42. I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you!
    business analytics course in hyderabad
    data science course hyderabad
    data analytics courses in hyderabad

    ReplyDelete
  43. Excellent Blog! I would like to thank for the efforts you have made in writing this post. I am hoping the same best work from you in the future as well. I wanted to thank you for this websites! Thanks for sharing. Great websites!
    Artificial Intelligence Training In Hyderabad

    ReplyDelete
  44. Clicksud este platforma de divertisment finală pentru seriale online și filme online. Divertismentul digital din întreaga lume este acoperit de clicksud și ne îndreptăm spre una dintre cele mai bune platforme online care înțelege nevoia publicului și oferă exact lucrurile vizitatorilor, ceea ce le face unice pentru noi.

    ReplyDelete
  45. I’m excited to uncover this page. I need to to thank you for ones time for this particularly fantastic read!! I definitely really liked every part of it and i also have you saved to fav to look at new information in your site.
    Data Science Training in Hyderabad | Data Science Course in Hyderabad

    ReplyDelete
  46. You are in point of fact a just right webmaster. The website loading speed is amazing. It kind of feels that you're doing any distinctive trick. Moreover, The contents are masterpiece. you have done a fantastic activity on this subject!
    Business Analytics Course in Hyderabad | Business Analytics Training in Hyderabad

    ReplyDelete
  47. I feel really happy to have seen your webpage and look forward to so many more entertaining times reading here. Thanks once more for all the details.
    Data Science Training in Hyderabad | Data Science Course in Hyderabad

    ReplyDelete
  48. Nice blog. I finally found great post here Very interesting to read this article and very pleased to find this site. Great work!
    Data Science Training in Pune
    Data Science Course in Pune

    ReplyDelete
  49. this blog was really great, never seen a great blog like this before. i think im gonna share this to my friends..
    data science course in guwahati

    ReplyDelete
  50. Very interesting blog. Many blogs I see these days do not really provide anything that attracts others, but believe me the way you interact is literally awesome.You can also check my articles as well.

    Data Science In Banglore With Placements
    Data Science Course In Bangalore
    Data Science Training In Bangalore
    Best Data Science Courses In Bangalore
    Data Science Institute In Bangalore

    Thank you..

    ReplyDelete
  51. I really like your take on the issue. I now have a clear idea on what this matter is all about.. buy like

    ReplyDelete
  52. I have to search sites with relevant information ,This is a
    wonderful blog,These type of blog keeps the users interest in
    the website, i am impressed. thank you.
    Data Science Course in Bangalore | Data Science Training in Bangalore

    ReplyDelete
  53. Clicksud shows: www.pinoy1channel.com/, TVpenet shows, rulare shows, Romanian shows full hd episodes online for free.

    ReplyDelete
  54. It has fully emerged to crown Singapore's southern shores and undoubtedly placed her on the global map of residential landmarks. I still scored the more points than I ever have in a season for GS. I think you would be hard pressed to find somebody with the same consistency I have had over the years so I am happy with that.
    Data Science Course in Bangalore

    ReplyDelete
  55. You might comment on the order system of the blog. You should chat it's splendid. Your blog audit would swell up your visitors. I was very pleased to find this site.I wanted to thank you for this great read!!
    Data Science Training in Bangalore

    ReplyDelete
  56. Then the article considers three obstacles that often discourage companies from making their ERP dream a reality: (1) companies must find the right software partner, (2) they need to review their current business processes, and (3) they have to deal with the cost factor. But first, let us look into the considerable benefits of ERP software, ultimately, trumping any challenges. download google input tool offline

    ReplyDelete
  57. I will really appreciate the writer's choice for choosing this excellent article appropriate to my matter. Here is deep description about the article matter which helped me more.
    Best Institute for Cyber Security in Bangalore

    ReplyDelete
  58. Very nice blog and articles. I am really very happy to visit your blog. Now I am found which I actually want. I check your blog everyday and try to learn something from your blog. Thank you and waiting for your new post.
    Cyber Security Training in Bangalore

    ReplyDelete
  59. Thumbs up guys your doing a really good job. It is the intent to provide valuable information and best practices, including an understanding of the regulatory process.
    Cyber Security Course in Bangalore

    ReplyDelete
  60. After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article.
    Ethical Hacking Course in Bangalore

    ReplyDelete
  61. This comment has been removed by the author.

    ReplyDelete
  62. Wow! Such an amazing and helpful post this is. I really really love it. I hope that you continue to do your work like this in the future also.
    Ethical Hacking Training in Bangalore

    ReplyDelete
  63. I am impressed by the information that you have on this blog. Thanks for Sharing
    Ethical Hacking in Bangalore

    ReplyDelete
  64. Actually I read it yesterday but I had some thoughts about it and today I wanted to read it again because it is very well written.
    data science course
    data analytics course
    business analytics course in hyderabad

    ReplyDelete
  65. Very interesting blog. Many blogs I see these days do not really provide anything that attracts others, but believe me the way you interact is literally awesome.You can also check my articles as well.

    Rowe Rowe
    Rowe Rowe
    Rowe Rowe
    Rowe Rowe

    Thank you..

    ReplyDelete
  66. If your looking for Online Illinois license plate sticker renewals then you have need to come to the right place.We offer the fastest Illinois license plate sticker renewals in the state.data science course in malaysia

    ReplyDelete
  67. The Basics You Have Explained Was Good.Thanks For Sharing The Content With Us.

    Python Training Course Institute in Hyderabad

    ReplyDelete
  68. Very impressive and interesting blog found to be well written in a simple manner that everyone will understand and gain the enough knowledge from your blog being much informative is an added advantage for the users who are going through it. Once again nice blog keep it up.

    ReplyDelete
  69. Very impressive and interesting blog found to be well written in a simple manner that everyone will understand and gain the enough knowledge from your blog being much informative is an added advantage for the users who are going through it. Once again nice blog keep it up.

    Data Science Course in raipur

    ReplyDelete
  70. Very impressive and interesting blog found to be well written in a simple manner that everyone will understand and gain the enough knowledge from your blog being much informative is an added advantage for the users who are going through it. Once again nice blog keep it up.

    Digital Marketing Course in raipur

    ReplyDelete
  71. If your looking for Online Illinois license plate sticker renewals then you have need to come to the right place.We offer the fastest Illinois license plate sticker renewals in the state.
    360digitmg

    ReplyDelete
  72. Found your post interesting to read. I cant wait to see your post soon. Good Luck for the upcoming update. This article is really very interesting and effective, data science courses

    ReplyDelete
  73. Pinoy Channel Filipino teleserye replays channel to watch all pinoy lambingan and pinoy tambayan , free and online pinoy tv .

    ReplyDelete
  74. I see some amazingly important and kept up to length of your strength searching for in your on the site
    artificial intelligence course in delhi

    ReplyDelete
  75. Our website serves as the best site where people can easily enjoy all the Pinoy TV and We gave them a chance to add a bookmark to their favorite site.

    ReplyDelete
  76. I have to search sites with relevant information ,This is a
    wonderful blog,These type of blog keeps the users interest in
    the website, i am impressed. thank you.
    pmp training in bangalore

    ReplyDelete

Popular Posts

Followers