Making tasks super inefficient.

So, we have to write about efficiency. Well, instead of doing what most people are doing, which is likely explaining what it is etc., my goal in this blog is to take a bunch of familiar concepts in programming, and write the most inefficient code I can think of in order to demonstrate some key ideas.

Big O

First though, I feel obliged to give the coles notes version of the notation we will be using in this discussion, "Big O" notation. We can pretend it's some kind of magic mathematical voodoo, or we can just think of it like I do, Lazy man equations.

What do I mean by lazy man equations? Well imagine you are someone who wants to use an equation to describe how well something he made works, but he hates actually sitting down and formulating a precise equation. So the lazy man says "well, it's pretty close to this" and that's what we get. For example, let's say the precise equation for something is that it takes n(n+1)/2 operations for some n. Well, we would say "it's pretty close to n^2" so we say it is O(n^2). Or perhaps it is e^n+n^99, eventually e^n will be the biggest, and we don't really care that the base number is e since we are lazy, so we just say it is O(a^n).

So let's get to the meat of this post shall we?

Crappy Sorting

So how could we sort really poorly?

Let's imagine we have a list with items in it, for example [4, 1, 3, 2].

I can think of one insanely bad way. How about we check if it is sorted... and then we randomize the list and check if it is sorted again?

[4, 1, 3, 2] not sorted! go again!
[4, 3, 2, 1] not sorted! (wrong order) go again!

etc.

So how can we describe this in our lazy man notation?

Well the fastest it could work is one iteration, so the best case we would describe as O(1). The average it would work, is about O(n!) which is pretty bad.

But oh, what about the worst case???? Well it is within the realm of possibility that it may never work, so we would actually say O(∞).

Truly a terrible algorithm.

Crappy Prime Number Checker.

Let's say we want to find if a number is prime. Well the first way you would imagine is to just check if every number before it divides into it. The way a computer would probably do this is with modulo, so we can think of it integer dividing + 1 each number p n//p +1 times. So for every p up to n this roughly works out to n + n/2 + n/3 + n/4 ... + n/n etc, which would be approximately O(n^2).

This is pretty crappy, since we can actually eliminate a whole bunch of numbers simply by realizing that we only need to check up to sqrt(n). Which actually means that our algorithm is n/2 + n/3 + n/4 ... + n/sqrt(n) however this is STILL O(n^2), although some might say that it is "subquadratic" but that is another topic for another day.

And for a change of pace... the world's most efficient sorting algorithm.
(courtesy of StackOverflow):

Presenting Intelligent Design Sort:

Introduction

Intelligent design sort is a sorting algorithm based on the theory of intelligent design.

Algorithm Description

The probability of the original input list being in the exact order it's in is 1/(n!). There is such a small likelihood of this that it's clearly absurd to say that this happened by chance, so it must have been consciously put in that order by an intelligent Sorter. Therefore it's safe to assume that it's already optimally Sorted in some way that transcends our naïve mortal understanding of "ascending order". Any attempt to change that order to conform to our own preconceptions would actually make it less sorted.

Analysis

This algorithm is constant in time, and sorts the list in-place, requiring no additional memory at all. In fact, it doesn't even require any of that suspicious technological computer stuff. Praise the Sorter!

Feedback

Gary Rogers writes:

Making the sort constant in time denies the power of The Sorter. The Sorter exists outside of time, thus the sort is timeless. To require time to validate the sort dimishes the role of the Sorter. Thus... this particular sort is flawed, and can not be attributed to 'The Sorter'.

Heresy!