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.)
| n | Constant O(1) | O(log n) | Linear O(n) | Linear Logarithmic O(n log n) | Quadractic O(n2) | Cubic O(n3) |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 2 | 2 | 4 | 8 |
| 4 | 1 | 2 | 4 | 8 | 16 | 64 |
| 8 | 1 | 3 | 8 | 24 | 64 | 512 |
| 16 | 1 | 4 | 16 | 64 | 256 | 4,096 |
| 1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |
| 1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 1012 | 1016 |
Java code example:
Show examples of notations in the table above.
Common Data Structures and Relative functions: Lists and Sets:
| Structure | get | add | remove | contains |
|---|---|---|---|---|
| ArrayList | O(1) | O(1)* | O(n) | O(n) |
| LinkedList | O(n) | O(1) | O(1) | O(n) |
| HashSet | O(1) | O(1) | O(1) | O(1) |
| LinkedHashSet | O(1) | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) | O(log n) |
Thanks to reader comments, the add method on an ArrayList should be: O(1) amortized (and O(n) in worse case). Useful reference links:
Maps:
| Structure | get | put | remove | containsKey |
|---|---|---|---|---|
| HashMap | O(1) | O(1) | O(1) | O(1) |
| LinkedHashMap | O(1) | O(1) | O(1) | O(1) |
| TreeMap | O(log n) | O(log n) | O(log n) | O(log n) |
Algorithmic Complexity and Big-O Notation.
Hi,
ReplyDeletethanks 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 :).
Thanks for the comments and from what i read, you're right.
ReplyDeletebut
:) yeah I tried to keep it simple, practical and easy to remember, so wanna stay away from the painfully technical details
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.
ReplyDeleteSee
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
Thanks for the input Philip. Yeah, I'll make mention and add the links you mentioned, very helpful.
ReplyDeleteGreat 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.
ReplyDeleteThanks
Javin
Why wait() and notify() method must be called from synchronized context
Very nice post. The cleanest I've ever seen so far.
ReplyDeleteThanks.
Alin
Nice summary. While many implementations like to capture the theory of big-O; the associated cost of O(1) is often ignored.
ReplyDeleteThe 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.
There's one part that is either wrong, or I am crazy.
ReplyDeletewhile (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.
Well written, it was extremely helpful and easy to understand.
ReplyDeleteThanks, nice and clearly explained. Another good one on Big O:
ReplyDeleteBig O Notation
Great article, thank you!
ReplyDeleteOne 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."?
nice post and great information shared
ReplyDelete12th Class Result 2016
keyresult
10th Class Board Exam Result 2016
The issue comes, on the off chance that they just keep a reinforcement on the server. ExcelR Data Science Courses
ReplyDeleteGet 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..!
ReplyDeletewatch your favourite pinoy tambayan replays online in hd. All the pinoy channels and all the replays you will be watch online in hd.
ReplyDeleteThanks for sharing this information. I really like your blog post very much. You have really shared a informative and interesting blog post with people.
ReplyDeleteremote developer jobs
watch all your favourite teleserye shows online on Pinoy Channel Tv free episodes in Single click full pinoy tv replays
ReplyDeleteI 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
ReplyDeleteGet all the latest clicksud online seriale online of clicksud and all the seriale online daily on this blog.
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
ReplyDeleteGreat Content, If you wish to upskill yourself in the latest Technologies Do visit GoLogica Trainings
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteNice post and valuable information thank you.
ReplyDeleteData Analytics Course in Pune
Nice post and valuable information, writing is simply great, thanks for sharing.
ReplyDeleteBusiness Analytics Course in Pune
Business Analytics Training in Pune
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.
ReplyDeletedata science course in indore
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.
ReplyDeletedata science course in coimbatore
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!
ReplyDeletedata science course in gurgaon
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.
ReplyDeletedata science course in bhilai
I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
ReplyDeletedata science course in nagpur
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
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteI feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
ReplyDeletedata science course in nagpur
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.
ReplyDeletedata science course in lucknow
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.
ReplyDeletedata science course in kanpur
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.
ReplyDeletedata science training in navi mumbai
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!
ReplyDeletedata science course in kochi
Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
ReplyDeletedata science course in pune
Nice post and great information thank you. waiting for the next update.
ReplyDeleteData Science Course in Pune
Data Science Training in Pune
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!
ReplyDeleteData Science Institute in Bangalore
Nice post and great information thank you. waiting for the next update.
ReplyDeleteData Science Course in Pune
Data Science Training in Pune
I have to search sites with relevant information ,This is a
ReplyDeletewonderful blog,These type of blog keeps the users interest in
the website, i am impressed. thank you.
Data Science Course in Bangalore
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.
ReplyDeleteBusiness Analytics Training in Hyderabad | Artificial Intelligence Course in Hyderabad | Business Analytics Course in Hyderabad
Very informative post! Here is a lot of information that can help any business start a successful social media campaign!
ReplyDeleteData Science Course
I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
ReplyDeleteData Analytics Course in Pune
Data Analytics Training in Pune
I am impressed by the information that you have on this blog. It shows how well you understand this subject.
ReplyDeleteBusiness Analytics Course in Pune
Business Analytics Training in Pune