Our favourite hobbies, like baking cookies or painting pictures, take time. Let's ask a question though, does it take longer to bake one cookie or paint one picture? It's hard to answer. But, we do know that baking one cookie would be silly. We tend to bake a lot of cookies at once.
There's something curious about baking cookies. If we want to bake more, we add more ingredients: more flour, sugar, and definitely chocolate. Adding and mixing those extra ingredients doesn't take more time. Scooping out and forming all the cookies does take more time, though not that much. It takes a long time to find the ingredients, get out the utensils, mix, bake, and then clean. The extra scooping for more cookies doesn't add much at all.
Compare this to painting a picture. We don't paint several pictures at once. Each picture starts with a blank canvas, and we need to redo all the work we did with the previous picture. Unlike the cookies, we can't just add more paint and brushes and get more paintings.
We can still compare these two activities. We aren't sure if painting one picture takes longer than baking one cookie. But we're confident that painting 12 pictures takes longer than baking 12 cookies. As the number increases so does the time difference. 100 paintings take much longer than 100 cookies. Indeed, 100 cookies don't take much longer than 12 cookies -- provided you have a big enough bowl.
By this logic, we can say that painting pictures is slower than baking cookies. This is what "time complexity" lets us do. Take process, we call them "algorithms", and compare whether one is faster than the other.
Let's look at another example. You're new in a class and want to introduce yourself to the others. You walk up to each kid, say "hi", and give them your name. You don't ask their name since you'll likely forget that anyway. If there are 30 people in the class, you will have to say "hi" 30 times.
What if you don't feel like saying "hi" so much? You could stand in front of the class and say your name. It wouldn't matter how big the class is. 30, 60, or even 100 people, you'd only have to say your name once. That seems like an efficient option.
What if you show up during recess? All the other kids are running around and making noise. Shouting "hi" is not likely to get their attention. You still have the option of greeting them each individually, but that feels like too much effort. Is there another way?
Yes, there is. You can say "hi" to two other kids and give them your name. You're also going to tell each of them to go find two more children, say "hi" on your behalf, and give them your name. Those kids, in turn, will do the same thing. These exchanges balloon. First you say "hi", then two kids say "hi", then 4, then 8, then 16, and doubling each time. You can reach a lot of people with little effort.
Without using a watch, we can say something about how long each approach takes. When you talk to each person directly, we call it "linear time", there are 30 kids, and you must talk to all 30 of them. Each extra child requires you to say "hi" once more. Standing in front of the class and shouting your name is called "constant time". It doesn't matter how many kids there are; the effort is the same. In the final approach you tell two kids, and they tell two, and so on. This is called "logarithmic time". Don't worry much about what that means. It's faster than "linear time", but slower than "constant time".
That's what "time complexity" is. It lets us talk about how long something takes without counting minutes and seconds. It helps us programmers find faster ways of doing things. And it's a great way to convince mom to bake more cookies.
Top comments (0)