Big O Help

Question

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.

Answer 1

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

Answer 2

We have a lesson on this btw. :>

https://www.sololearn.com/learn/6362/?ref=app

Answer 3

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

Answer 4

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.

Answer 5

All your answers are extreemly helpful! Thank you everyone!

Answer 6

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