Big O Help
Hey guys. I am trying to understand Big O in general. I sort of know the basics, seen the graphs, but struggle to find real world examples. I feel this would help me grasp it even better. Any real world examples of O(1),O(log n),O(n),O(n^2). Any guidance/ story appreciated.
2/22/2019 3:17:48 AMCameron Hansen
6 AnswersNew Answer
Ok a real world example: Imagine one day you open your email and there are hundreds of unread emails. Lets say you are required to read each 1 and send a reply. If you start at the bottom (or top) you can find it in O(1) time (just the next one in the list). To read and reply to all, there are n emails so for all of them its O(n), 1 * n. If you decide to reply to the most urgent first. Then you will have to search through n emails just to get the first 1, so this is O(n). When you do it for all n emails it will be O(n^2), n*n. (The fact that the list is shrinking as you go through it decreases the searching by halve but it's still O(n^2)). If you have a list people you have ordered by the priority to have to reply in, and the computer orders the emails by name of the sender; then you can find the all (if any) from the person at the top of the list using binary search. (Like looking up words in a dictionary.) This would be O( log(n) ). Then if you do this for all n emails it would be O( n log(n) ).
We have a lesson on this btw. :> https://www.sololearn.com/learn/6362/?ref=app
So perhaps this works: a friend gives you CDs, and wants you to burn 10 songs. If you burn them all on 1 CD that is O(1); 2 per CD, so 5 Cds in total is O(log n); O(n) might be where you burn 1 song per CD; I don't know what O(n^2) would be? O (n log n ) is where another friend wants those same songs too so you do 2 songs per CD for each friend. Are these correct? I thought I would give it a shot before I ask for help. Thank you for any help.
Well OK there are a few assumptions for the last case, but I think its pretty good.
All your answers are extreemly helpful! Thank you everyone!