Someone on reddit had a small Computer Science question that was, to be quite honest, stupid simple with a bit of reasoning.  They deleted their post (good on them really) before I could give them my answer, so here it is for you.

Q: "A sort (such as a bubble sort or insertion sort) is O(n2). 1000 records are sorted in 1 second. How long does it take to sort 3000 records?"

Can someone explain "O(n2)" to me? please? :)

I'm studying for a final in an intro to comp sciences class, and something that I never understood was this O(n2) thing.

The example he gives is of sorting records. On the last (midterm) exam, the question arose:

"A sort (such as a bubble sort or insertion sort) is O(n2). 1000 records are sorted in 1 second. How long does it take to sort 3000 records?"

I could not for the life of me figure out how he came to 1 second from 1000 records. (and I got the answer wrong :\ )

Could anyone explain this to me, pretty please? I'd appreciate it!

A: 9 seconds.

n is the number of records to deal with. O(n^2) means that running time will be exponential.  In other words, for 3000 records your program will execute the inner loop body 3000^2 or 9,000,000 times.

Luckily, your prof gave you a rate.  Unfortunately, the dim-witted will think this is linear and say, "1000 records in a sec, then it'll be 3 secs for 3000!" which is quite wrong.

Keeping in mind that when n = 1000 then n^2 = 1,000,000.  According to the problem, 1,000,000 operations takes 1 second, so the sort on 3000 items should take 9 seconds.

I've been programming for a long time.  Not as long as many others, but long enough to be considered an old-timer.  I took tenative steps into the programming world when I was 13 or so when I caused an infinite loop in QBasic.  I'm now a 27-year-old C# web developer.  So, when I peruse a "Beginning Programming" book and find "You can't hurt your computer..." I become enraged.

First, I understand that the point of such a statement is to instill confidence in the beginner.  I might even be able to overlook it.  But that author went a step further, say, "Computer Science is not math."  Truth is that it is math, but most programming languages choose to hide this from you.  It's not conventional math by any stretch of the imagination, but it is a method of mathematical expression.  It has a certainty and precision that is clinical in nature and mathematical in form.

So, for the budding programming, I write these overviews in order to clarify ideas and concepts.  I am initially writing to an audience exploring the programming world through C# since that is what I am immediately familiar with, but will expand this to other langages as I will.  Most of the concepts that I write about will break language barriers, but others will have special cases.  These cases are either shortcuts built into the langage or powerful features that the designers thought would be useful.

But I will not lull you into a false sense of self-confidence.  If you are working with File System libraries then you can destroy your operating system.  That's the name of the game when you're dealing with powerful things.  The idea is that you learn to control them and, by doing so, build your confidence through action.

So, let us begin.

Programming Basics:  Integers and the Assignment Operator

The most important concept to understand in programming is putting a value from one place to another.  Let us consider an example.

int x = 1, y = 2;

x = x + y;

In math, the above is nonsense.  This is okay since it is not a mathematical statement of equality.  It is a statement of assignment that could be written more along these lines:

x <- x + y;

What this is saying is "put the value of the expression x + y into x". "x" is actually a space in memory allocated in the first line.  This space in memory has a type given at declaration.  "int" stands for Integer, which is a whole number.  After our assignment statement is evaluated, the value of "x" is 3.

There isn't much that we can do with only this, but it does give an idea of where we start.  You can try the example with all the arithmetic operations (+ addition, - subtraction, * multiplication, / division).

Tutorial 1 - IntegersAndAssignment.zip (23.35 kb)

So the end of March is coming fast, the weather is starting to get nice, and taxes are just around the corner.  My most not favorite time of the year.  It's good in the sense that cold weather is only enjoyable for a week or so, but bad as in I barely have enough to keep my house above freezing and eat.  Such is life.  In any event, I'm bouncing off the walls thanks to the warm up and then the cool down.

Also, I've noticed that there really is an uptick in comment spam on BlogEngine.net blogs.  Maybe it's because of the very clean nature of the markup it produces or the services it pings with updates.  Regardless, the initial comment filter really is inadequate.  Hopefully that will change as it develops more of a history and boots the spam more reliably.

I can only dream.