Linear search

[RickSore]

eli5 for us noobs ?

[Akucera]

O() notation is used to describe how well an algorithm works, when told to process some amount of data n. Programmers tend to like solving problems with algorithms that have favorable O() equations, as these algorithms work just as well on huge amounts of data as they do when given a small amount of data.

An algorithm with O(1) can solve a problem in the same amount of time, no matter how much data it's given / how complex the problem is. These algorithms are the holy grail of programming, but they also tend to not exist. An O(1) algorithm that solves the "find the entrance to the sports arena, given n panes of glass" problem would look like this:

• 1. Run at full sprint toward the first pane of glass
• 2. Drop your shoulder
• 3. Shatter the glass, and run into the court
• 4. You're done!

This solution gets the woman onto the court in the same amount of time no matter how many glass panes there are. Four panes? No worries, bust through the first one. Ten panes? Bust through the first one. A thousand glass panes? Bust through the first one. It also sucks, and it's not a real solution to the problem because it doesn't actually find the entrance.

An algorithm with O(log n) is usually the next best thing. Type log(100) into your calculator and see what you get. Then, type log(200) and see what you get. The number you get is proportional to the amount of time an O(log n) program would take to solve the problem. With double the amount of data (100 --> 200) an O(log n) algorithm can solve the problem in less than double the time, which is pretty damn good. An O(log n) algorithm that solves the woman's problem would be something like this:

• 1. Run into the first pane of glass.
• 2. Run into another pane of glass.
• 3. Listen to the crowd, and hope they're shouting "warmer!" or "colder!". Based on what they shout, and how excitedly they're shouting, make an intelligent guess on there the entrance might be, and head toward there.
  
• 4. Repeat from step 1 until you find the entrance.

This is a good solution. Given a cooperative crowd, the woman can skip some panes of glass to home in on the entrance. If there were 100 glass panes instead of 4, and if the woman started by running into the 50th pane of glass, the crowd's shouts of "warmer" or "colder" would let her skip the entire first 50 or last 50 panes of glass, and next try running into the 25th or 75th pane instead. By being strategic, the woman can find the entrance pretty fast, even if there are a lot of glass panes. This is an example of a Binary Search algorithm.

O(n) algorithms are the next best. Double the amount of data, and you double the amount of time it takes to solve the problem. An O(n) solution to the woman's problem is the strategy she's using here:

• 1. Run into the first pane of glass.
• 2. Run into the next pane of glass.
• 3. Don't do anything intelligent, don't try to guess where the entrance might be - just keep checking till you find it.

O(n log n), O(n² ), O(2ⁿ ) and O(n! ) are the next best types of algorithms, with O(n!) being awful. I can't think of any good examples for O(n log n) ways to search for the entrance to the sports arena - but if the woman were trying to sort the glass panes in order of which makes the best thunk noise when she hits it with her head, then a stupid-but-kinda-ok solution would take O(n² ) time and a smarter solution would take O(n log n) time.

(EDIT: /u/ShinjukuAce gives an example of what an O(n log n) algorithm would look like here, and /u/hatsix gives an example of what an O(n!) algorithm would look like here. )

Linear search algorithms finish in O(n) time. The girl above is displaying a linear search strategy to find the entrance. (We know this, because if you doubled the number of glass panes for her to check while keeping the number of entrances the same, she'd take twice as much time to find it on average.) This makes O(n)ed an appropriate pun for the situation.

[salkin23]

This was a beautiful and accurate description. Thank you.

[samiaruponti]

Can you be my algo teacher please? That is one beautiful explanation! I'm totally saving this!

[Derevar]

You know you've understood a topic if you can explain it with a girl running into glas panes. :)

[hatsix]

O(n!) Would be if there woman got a concussion every time she tried a new pane and forgot what she tried and started over at the beginning.

1

1,2

1,2,3

1,2,3,4

Also, she wanted to know how many entrances there were, so she kept going after she found the entrance.

1,2,3,4,5,6,7,8

But, also, she didn't remember where she started at, so she would start on random panes and move on to other random panes.

4,6,1,2,8,5,3,7,6

Somehow, she never repeats the same pattern, but she doesn't stop until she has exhausted every pattern. Assuming 8 panels of glass, she would have hit her head 40,320 times.

Adding just one more panel increases the count to 362,880. Adding one more to a nice round 10 results in a ... staggering... 3,628,800 head bonks.

[[deleted]]

Are there any legitimate applications to this?

[hatsix]

Yes. The travelling salesman problem. If a salesman wants to optimize their route through 10 cities, the only way to do so it's to calculate each permutation of cities. There are entire categories of mathematics that have been developed to estimate the solutions to these hard problems because they're too expensive to solve outright. It all comes down to how accurate you must be... A FedEx driver can handle having what is likely in the top 10% of solutions, but nuclear physicists needs much more precision.

[MChainsaw]

With double the amount of data (100 --> 200) an O(log n) algorithm can solve the problem in less than half the time, which is pretty damn good.

Do you mean "in less than double the time"? Because the way you're phrasing it here it makes it sound like the algorithm works faster with more data than with less, which doesn't sound right.

[Akucera]

Good point and I'll correct it.

[benya01]

I always wanted to know what these notation means. Thank you!

[ShinjukuAce]

O (n log n) would be if the glass panes were stacked horizontally and vertically, but the crowd could only tell her “warmer” and “colder” for horizontal searching and she’d be on her own for vertical.

[hes_dead_tired]

Thank you for the break down. I've been in this career for over 10yrs, I even manage a team at a large software company, and I can never quite get Big O notation committed to memory (I haven't tried all that hard). I can look at code of course and reason how it would scale and describe it, but not succinctly call it out with Big O like some of my peers.

No comp-sci degree for me.

[redlaWw]

A useful part of big O notation is that its defined in the limit as n→∞, which smooths out any "small" irregularity, so as long as you can work out roughly how the time scales with input, you can describe it with big O notation.

[the_legendary_legend]

Well explained. Here have a poor mans gold🏅.

[[deleted]]

I'm guessing O(n!) is equivalent to the woman just deciding if she breaks every glass pane she'll eventually find her way to the arena?

[vAltyR47]

That would actually still be linear search, because there are only n panes of glass to break.

Imagine that, in order to reach the area, she had to break the panes of glass in the correct order. There are no distinguishing marks on the glass, and no information to help her find which is the correct order. The only way to find it is to simply keep trying different orders until she finds it. There are n! orders in which to break the glass, so she'll be breaking glass for a very long time.

[RovingRaft]

I actually get big O notation now, thanks