O(n) our way

Now that we have a basic overview of Big-O notation, I think the best way to build understanding will be to learn by going through each of the most common complexities.

Part 2: O(n)

The first big-o function we're going go look at is O(n), also known as linear time.

Hypothetical Catering Company

Lets pretend you own your own catering company. You recently scored a contract with a local business to provide food for all their corporate meetings and events!

But, you're not just a caterer. You're also a coder! So before we do anything, we're going to map out our algorithm so make our meal as efficient as possible.

Let's write some pseudocode (in ruby cause I like it most)

# n = number_of_people

def cater_party (n)
   # whatever we're going to do
end

There are a couple of ways you could handle this event, but let's say you decide to make a meal for every person in attendance.

Lets update our pseudocode

# n = number_of_people

def cater_party (n)
   n.each do |person_at_party|
      # plate some chicken
      # plate some side dishes
      # etc
      return full_meal
   end
end

If 1 person shows up, you make 1 plate
If 10 people show up, you'll need to make ten plates
If 10,000 people show up, you'll have to cook and prepare 10,000 separate meals!

We can see that as the number of people who are come to the event increases, the plates we need to make also increases by a constant amount. In this case 1 more person means 1 more meal to make.

Intuitively, it's pretty easy to see how our workload grows related to the number of people. Our workload increases by a constant amount for every new person.

This is the relationship expressed by O(n).

Constants

If we think about our catering meals example, there was a lot of extra work we left out. What about all the set-up? What about providing the drinks? What if we had to make a dinner and a desert plate?

Really our catering pseudocode might look more like this:

# n = number_of_people

def cater_party (n)

   # cook all the food
   # drive to the venue
   # set up 

   n.each do |person_at_party|
      # plate some chicken
      # plate some side dishes
      # do it again for desert
      # get them a drink
      # etc
      return full_meal
   end
end

Shouldn't we take those things into account?

First, remember that we're talking about big-o, and big-o only describes how the complexity grows as the input size increases.

Does the number of people affect how much set-up we have to do? Not really.

Does it affect our drinks? No, we'll just put out a dispenser.

Is doing 2 plates per person affected by the number of people? This one is tricky, and you may be tempted to say yes, but really think about it. Yes, creating a full course for each person is twice as hard, but we still expect the same increase in work per person. If you consider both dinner and dessert as one "meal", then we're right back to a 1 to 1 increase.

All these extra things are constants. Since they stay the same relative to our input size, we can mostly ignore them when determining the basic big-o complexity for a given algorithm.
Sure, you can add them in to be more precise, but just know that as "n" gets bigger, the effect of constants shrinks.

More about O(n)

I mentioned in the beginning that O(n) is also called linear time. That's because if you plot O(n) on a graph with number of items (n) on one axis, and number of operations (O) on another, you'll get a straight line like below:

Next Time

O(n) is a the baseline when it comes to complexity (overall, not just tin coding). It's probably the most intuitive, and one of the easiest big-o functions to understand.

Next time, we'll look at the notation for the least complex algorithms.