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)

Okay, so WOAY didn't launch yesterday.  That's the speed of business.  Fortunately, they did launch today, and the phones were buzzing almost three times an hour.  Ah, a typical launch!

So, I've gotten most of that website buttoned up, meaning that there are a few minor glitchy parts that I need to visit (the search button overriding everything for a start) but it's pretty much up to snuff as far as I'm concerned.  Considering that I'm up to my eyes in work from other sources (that will remain nameless and unknown until such a time as it's too late) it's likely that it will be awhile before I get around to fixing minor glitches.  In any case, there are greater problems to be crushed!

For instance, implementing a git source control repository on Windows 2003 server so that Jeff and I don't go completely insane trying to manages merges of code through the file system, not to mention the organization of older codefiles that such a repository brings.

But I guess my biggest problem at the moment is arguing the merits of Free Software in a Microsoft centric, the more you pay the better it is, crowd.  For some things, I could see paying out the nose for solutions that involve project management or libraries.  I even think that .NET is a decent platform.  However, when I see the things that people do with languages like Python, Ruby, Perl, and, dare I say it, PHP, it makes me wonder how I strayed so far from that path.  And I sometimes wish that I hadn't.

Sure, .NET has its share of open source projects.  DotNetNuke, mojoPortal, BlogEngine.NET (which runs this site), and others that may or may not be related to the web stand as proof.  But given the three projects I mentioned by name, the most straightforwardly customizable one among them is BlogEngine.NET, and its default theme leaves much to be desired on that front, cramming everything into a single CSS file without any guide to what its controls actually use and where styling for the theme itself begins.  mojoPortal is a complete nightmare to use in such a context, and DotNetNuke doesn't win any favors from me.  There are others, but they are open source in a very loose sense, and I have no experience with them.  May not be a fair assessment, but there it is.

With any luck there will be greater improvements on these systems and frameworks (such as ASP.NET MVC, which has greatly sparked my interest), though it will take some time.  Though I fear it may take too much given the rapid evolution of the other platforms due to their respective communities.  Well, not so much PHP.