beanz Magazine

P v NP: A Modern Mystery

Marco Tamma on Flickr

Can we measure the time and steps required for things to happen?

Programming may seem magical, but at some point almost every programmer is going to hit against one big limitation: time. You can “solve” any problem in the world, but if your code takes years to finish it’s not really a solution anyone can use.

Programmers and computer scientists like to talk about the complexity of programs, both space and time complexity. Space complexity is about how much memory the program uses or, in other words, how much data it needs. We’re not going to talk about this much, instead focusing on time complexity.

We don’t tend to measure time complexity in terms of time but rather in terms of how many steps something takes. Steps are a better measurement since the number of steps-per-second processors can calculate goes up every year, but the steps don’t change over time. Further, we don’t even need to be particularly exact in measuring how many steps the program takes. We just need a rough measurement in terms of the “size” of the problem we’re working on.

For example:

  • the length of the list we’re sorting
  • the number of accounts in the database we’re searching
  • the number of computers in the network when we plan how to efficiently send data over the internet
  • the number of variables in the system of equations we’re solving

To be specific, let’s consider a list of length n that we need to sort.

If we’re trying to figure out whether or not the sorting algorithm we want to use is feasible, or in other words it can finish in a reasonable time, we don’t actually care whether the number of steps an algorithm takes is 3*n or n + 100 or 20*n. What we care about is how fast the number of steps grows: whether it grows by 3*n or 20*n making the list ten times larger only makes the number of steps grow by a factor of ten. On the other hand, if your algorithm grows like 3*n^2 or 2*n^2 and you make the list ten times longer, it will take one hundred times longer to finish.


Become a subscriber and get access to the rest of this article. Plus all our magazine articles.

Stories also include numerous links to help parents, kids, and teachers learn more. Get access today at just $15 per year!

Subscribe Today!

Also In The June 2017 Issue

Can we measure the time and steps required for things to happen?

This Canadian experiment used a robot to explore how people respond to robots and technology.

An amazing new book turns math problems into shapes and illustrations.

This pen and paper project helps organize ideas into stories with a finite state machine.

While you can't use soap and water on your code, you can keep your code as sparkly clean as any dish or silverware.

This project explores the basics of using Google's Static Map software to display your own maps.

Most people love cookies. But these cookies are the kind that make the internet possible.

Links from the bottom of all the June 2017 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about computer science, software programming, and technology for June 2017.

Software languages don't magically appear. They're created by design. First in a series.