Wednesday, April 08, 2015

Levels of complexity (in the real world)

In CS school, we learned about computational complexity (and if you start tuning out you can just skip to the next paragraph). Some algorithms take "linear time" - an amount of time roughly equal to the data that you have. So if you have n pieces of data, computing on them will take about n units of time. (and if your data size doubles, it'll take twice as long.) Some take "quadratic time" - so if your data size doubles, it'll take 4 times as long. Some take "exponential time", like 2^n, so if your data set gets *just one piece bigger*, the program will take twice as long. (and of course you could fill in any other function; some things take n^3 time, or log(n) time, or whatever.) So you want to do as many algorithms that are "linear time" or "logarithmic time" (n, or log(n)) if possible, and avoid things that are quadratic if you can, and really avoid anything that takes exponential time.

In the real world, I feel like you get different kinds of complexity:
- problems with helpers
- neutral problems
- problems with adversaries
I am just making these up, this is not an official distinction or terms or anything.

Problems with helpers: these are great, and easy, and fun! Even if you don't do great, your thing will get done. An example: if you're a bigwig executive, and you can ask your secretary to book a plane ticket. Your secretary knows your preferences, they know all the billing info, all you do is tell them where/when you want to go. Another example: scheduling dinner with some friends. Even if you accidentally say the wrong place or time, you can call your friends and say "oops, I meant this other day", and they'll probably either arrange other things in their schedule to make it, or else just not make it and it's fine.

Neutral problems: kind of like you vs. the machine. Example: doing the laundry. Kind of difficult sometimes (and takes a long time), and if you put it on the wrong settings it'll mess up your clothes but (at least supposedly) you have all the information you need.

Problems with adversaries: these seem simple but turn out to be difficult because you have to account for all the ways your adversary *could* thwart you. Example: selling tickets online. The core thing is simple, but you have to account for the fact that some people might wire up some bots to grab all the tickets in one second and then scalp them, so it gets difficult. Or, counting votes. Simple process! But you ideally want to set it up so that even if you have one corrupt vote counter, the whole election won't be stolen.

Software tends to have adversaries, which is why most "simple" apps tend to take forever to build. Same with everything legal.

No comments: