**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(n
^{2}) 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(n ^{2}) | Cubic O(n ^{3}) |
---|---|---|---|---|---|---|

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 | 10^{12} | 10^{16} |

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

** 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:*

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

**References:**

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

I want to say thanks to you. I have bookmark your site for future updates.

ReplyDeletedata science course

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!

ReplyDeletebusiness analytics course in hyderabad

data science course hyderabad

data analytics courses in hyderabad

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!

ReplyDeleteArtificial Intelligence Training In Hyderabad

Clicksud este platforma de divertisment finalÄƒ pentru seriale online È™i filme online. Divertismentul digital din Ã®ntreaga lume este acoperit de

ReplyDeleteclicksudÈ™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.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.

ReplyDeleteData Science Training in Hyderabad | Data Science Course in Hyderabad

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!

ReplyDeleteBusiness Analytics Course in Hyderabad | Business Analytics Training in Hyderabad

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.

ReplyDeleteData Science Training in Hyderabad | Data Science Course in Hyderabad

Nice blog. I finally found great post here Very interesting to read this article and very pleased to find this site. Great work!

ReplyDeleteData Science Training in Pune

Data Science Course in Pune

this blog was really great, never seen a great blog like this before. i think im gonna share this to my friends..

ReplyDeletedata science course in guwahati

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.

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

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

ReplyDeleteI 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 | Data Science Training in Bangalore

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

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

ReplyDeleteData Science Course in Bangalore

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!!

ReplyDeleteData Science Training in Bangalore

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

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

ReplyDeleteBest Institute for Cyber Security in Bangalore

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.

ReplyDeleteCyber Security Training in Bangalore

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.

ReplyDeleteCyber Security Course in Bangalore

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.

ReplyDeleteEthical Hacking Course in Bangalore

This comment has been removed by the author.

ReplyDeleteWow! 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.

ReplyDeleteEthical Hacking Training in Bangalore

I am impressed by the information that you have on this blog. Thanks for Sharing

ReplyDeleteEthical Hacking in Bangalore

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.

ReplyDeletedata science course

data analytics course

business analytics course in hyderabad

https://digitalweekday.com/

ReplyDeletehttps://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

ReplyDeletehttps://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

https://digitalweekday.com/

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.

ReplyDeleteRowe Rowe

Rowe Rowe

Rowe Rowe

Rowe Rowe

Thank you..

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

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

ReplyDeletePython Training Course Institute in Hyderabad

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.

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

ReplyDeleteData Science Course in raipur

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.

ReplyDeleteDigital Marketing Course in raipur