- 1

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

6 Answers

+ 2

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

+ 6

We have a lesson on this btw. :>
https://www.sololearn.com/learn/6362/?ref=app

+ 5

https://www.sololearn.com/discuss/1353180/?ref=app

+ 1

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.

+ 1

All your answers are extreemly helpful! Thank you everyone!

0

Well OK there are a few assumptions for the last case, but I think its pretty good.