What In The Hell Is Big O

GOTO All What In The Hell Articles

Big O is a notation for describing the worst-case performance of an algorithm or procedure. This post will show real-world examples of big O notation.

 

O(1) – Constant Time

A constant time algorithm will always take the same amount of time to run.

Example:
Finding a book in a library.

Why:
There are many methods to finding a book in a library, but I’m going to stick with the simplest, ask the librarian.  Assuming the librarian is familiar with their library, it should take about the same amount of time to find a book about mathematics as it would about poetry.

For another example see indexing an array.

 

O(n) – Linear Time

A linear algorithm runs once for each item(n).

Example:
Finding a CD in a stack of CDs

Why:
The simplest method of finding a CD in a stack of CDs is to just look at the one on top.  If that CD is the one you’re looking for, you’ve found it.  If it is not, look at the next one.  Repeat until there are no CDs.  If the CD we’re looking for is the last one in the stack, we had to look at every CD to find it.

But what about all the times that you look for a CD and the CD you’re looking for is in the middle or on the top?  Big O notation describes the worst-case running time of your algorithm.  It assumes that every search will be for the last CD (or a CD that doesn’t exist).  Big O is not a statistical model of how often a given condition will occur in an algorithm!

 

O(log n) – Logarithmic Time

A logarithmic algorithm runs log2(n) times.

Example:
Let’s play a guessing game.  I’m going to pick a number between 0 and 100 and you have to guess it.  You have to try to guess the number in as few guesses as possible.  Every time you guess I will tell you if my number is higher or lower.

Why:
You could devise a number of strategies for playing this game, however one strategy is particularly good at this type of game, binary search.  Each time we guess, we guess the number right in the middle.  By doing this we halve the number of possibilities every time, let’s play a little game…

The game above plays out the worst case performance of an O(log n) algorithm like binary search.  Instead of making 100 guesses at worst, we only make 7!

 

O(n2) – Quadratic Time

A quadratic time algorithm runs n2 times, or n times for each n.

Example:
Check if there are any duplicates in a deck of cards.

Why:
The simplest way to check if there are any duplicate cards in a deck is to pick the first card from the deck. Then compare that card to every other card in the deck. If there are no matches take the second card from the deck. Then compare the second card to every other card in the deck. Continue until you have checked all the cards.

By the time we are done we have looked at each card in the deck 52 times for a total of (52 * 52) 2704 comparisons. There are ways to lessen this number, like not looking through cards that you have already compared. However the most important thing to remember with big O notation is that it always describes the worst-case time, not the average.

Here’s what the process looks like if you don’t re-check cards you’ve already compared.

I’ll come back later and add some more big O notations, so check back. For now I’ll leave you with a question to ponder. What is the big O notation of the diagram above?

Links

Sorting (this will be the topic of another WITH article, but for now…)

Visual Representation of Sorting Algorithms in Javascript

Visualizing Sorting Algorithms

sortvis

Parallel GPU Sorting (pdf)

What different sorting algorithms sound like

GOTO Table of Contents

Advertisements

What In The Hell Are Trees

GOTO All What In The Hell Articles

A tree is a hierarchical data structure that contains a set of nodes. The node is the the basic building block of a tree and to understand trees you have to understand nodes.

A node is a data structure that has a parent, can contain a value and can have 0 or more child nodes.  A node with no child nodes is called a leaf node, or more commonly just a leaf.

A node with no parent is referred to as a root node.

Each node can have a child node of its own.

A node can have more than two children too.

By now you should grasp the basic structure of a tree, but what are they good for and where are they used?  Well the good news is that trees are all around you.  Your operating system’s directory structure is a tree, HTML and XML are both trees.  Your filing cabinet could even be considered a tree.  A linked list is also a form of tree, where each node has exactly one child node.  Let’s take a look at some more trees.

You belong to a tree too!

and of course…

 

Implementation of Trees

Programming languages have varying levels of support for tree-like data structures.  The abstract idea of a tree and the implementation of one are often very different things.  Pretty much any nestable data structure can suffice for an ad-hoc tree implementation.  For example here’s one of the simplest trees you can implement in Python.

class Node:
  def __init__(self, value=None, *args):
    self.value = value
    self.children = args

# A tree can then be defined as
tree = Node('root', Node(1), Node(2))

Scheme makes it quite a bit easier, both code and data are represented using trees (actually lists).

(define tree (cons 1 2))
tree
;>>> (1 . 2)

(define nested-tree (cons 1 (cons 2 3)))
nested-tree
;>>> (1 2 . 3)

If you’re wondering why the nested-tree looks like a list, remember that lists are a subset of trees.

I didn’t get to heavily into how trees are implemented in any particular language.  Mostly this is because the implementations of tree data structures varies widely from one language to the next and sometimes there are even multiple implementations of trees in a single language.

Many decisions go into a tree implementation and the tools that work with them.   Because of this there are many different types of trees, each with its own strengths and weaknesses and tools for manipulating them.  Future WITH articles will will go deeper into trees, their implementations and characteristics.

GOTO Table of Contents

What In The Hell Are Functions

GOTO All What In The Hell Articles

A good way to think about functions is as machines. Machines are designed to repeat a process over and over again. Functions share a lot of characteristics with machines, so let’s look at some of the properties of machines we’re already familiar with.

Machines take input and produce output, let’s take a look at a few examples of that. Your dish washer takes dirty dishes as input and returns clean dishes as output, your washer does the same for clothes. Your radio takes radio waves as input and produces music on your speakers as output.

For the most part you don’t have to know how a machine works, you only need to know how to use it. For the moment we’re going to look at functions the same way, not thinking about how they work, just about how to use them. You’ll be happy to learn that you’re already familiar with a few functions, in fact here’s one you use every day.

Using the function above is simple. We don’t care how it works, whether it is carrying it’s ones or counting on its fingers. The only thing that matters to us is that we give it 2 numbers, 35 and 7 and it gives us back 42.

Here’s an example of another function. This one reverses any string that we give it.

 

Terminology

When we use a function it is referred to as calling that function. So in the above two examples we called the add function and we also called the reverse function.

The input to a function is referred to as the arguments or argument in the case of a single input. Adding arguments to the above we get, we called the add function with the arguments 35 and 7 and we also called the string function with Hello as an argument. Arguments are also commonly referred to as parameters and the two words can be used interchangeably.

The output of a function is most commonly referred to as the return value, though it is referred to as output as well.

 

Calling Functions

Now that we’ve explored some of the properties and terminology of functions let’s look at how they’re represented in code. Just like before, we are not going to worry about how the functions work just yet. We’re only going to call a few.

Function calls can be represented a number of ways, depending on the language you are using. However the vast majority of mainstream languages use this convention.

____________( ______, ______ )

Instead of a fill-in-the-blanks style as above, programmers usually use a shorthand for describing things that can be anything. Unfortunately there is no standardization for this shorthand, so to know what is a shorthand you need to know what words are never used as real names. The use of foo, bar and baz are commonplace and you will have to get accustomed to reading them eventually.

I will take another approach here. I’ll use prototypes to talk about the basic structure and I’ll use descriptive names in any code. This approach is used in many Scheme manuals and I have found it easy to grasp. For now a prototype will be a source code snippet with no line numbering and all the lines highlighted.

Lets start our introductions to prototypes with a prototype of the add function.

Prototype:

name(argument, argument)

Let’s look at the diagram for add and put these labels on it in red.

 

Function Arguments

Functions often take arguments of a specific type. For example the add function above only takes numbers. If you attempt to give it a string it will produce an error. In contrast the reverse function will only accept a string.

To make it easier for you to tell what type of argument to use, the prototypes will state the type.

add(number, number)
reverse(string)
length(argument)

Whenever the type of the argument does not matter or can be of multiple types the word argument will be used.

Let’s take a look at a few more functions and how calling them maps out onto our diagram. The first function we’ll look at is max it will take two numbers as input and give us back the largest one. First I’ll show you the prototype then the code used to call max followed by the diagram.

Prototype:

max(number, number)
max(35, 7)
#===> 35

You probably noticed the #===> symbol in the source code. # is a comment in Python, which is the language used for the psudo-code in this series. A comment is completely disregarded by the computer and is only meant for you to read. This series uses the ===> symbol to show you the output of the code that was just run.

Our next example is length which takes a list or string as input and produces the length of that list or string as output. Because it takes a list or a string, we’ll use argument in our prototype.

Prototype:

length(argument)
length("Hello")

Functions can take two different kinds of arguments too. Here’s a function that takes a string and a number as input and gives us back a letter. Its output is the same as finding the letter by starting at the beginning and counting each letter until you get to number then return that letter.

Prototype:

letter(string, number)
letter("Hello", 2)
#===> e

 

Writing Your Own Functions

I’m going to borrow from SICP here and start with a simple function called squared. This function takes one number as input and returns the result of multiplying that number by itself.

The first thing we’ll do is define what this function should do. You will most likely do this in your head, but here I’ll lay it out like I laid out the functions above. We know we need a number as input and the output should be that number multiplied by itself, so let’s start with a prototype, a fake call, and a diagram like before.

Prototype:

squared(number)
squared(4)
#===> 16

Now that we know what our function should look like when it’s finished, we have to define it. But before we can do that let’s define what a function is a little more precisely.

 

What is a Function

When we were using functions we could think of them as “black boxes” that we put input into and got output out of. Now that we’re writing our own we need to think about how our functions work. Remember that a machine is made to repeat a process over and over. Functions are exactly the same, they also repeat a process or series of processes over and over.

A function is both a set of directions for performing a task and a machine that performs that task.

The syntax for defining a function can vary widely between programming languages. Some languages require that you declare argument and return types. We’ll cover that a little bit later, for now we’re going to focus on the method used by Python.

To define a function in Python you must supply a function name and its arguments. Here’s the prototype of Python’s def form, followed by a definition of squared.

Prototype:

def name(argument, argument, ...):
  # body
def squared(number):
  number * number

There are two main concepts in the above code that we have not covered yet. The body of a function contains the code that describes the process of the function. It is in the body that the instructions for performing the function are held. When we call the function we will use the body, but for now it is just a description of the process.

squared(4)

When we call the function, the programming language looks up the instructions for the function, then replaces all the argument names with the arguments the function is called with. Here’s a simple view of what your programming language sees when you call squared(4).

def squared(4):
  4 * 4

As you can see the number argument is replaced by the 4 argument. Your programming language will do this behind the scenes for you, but you conceptually do this transformation in your head every time you write a function.

However there is one thing wrong with the above function. When we call it, it doesn’t give us back the answer. In fact it seems like it does nothing at all!

 

Returning Values

Most mainstream languages require the use of a return keyword to signal that you want to return a value. Python also requires a return statement so we’ll have to add one in to get the return value.

def squared(number):
  return number * number
squared(4)
#===> 16

 

Combining Functions

Now that we have a function squared that will square a number, let’s look at how to use that in another function.

We’re going to define a new function aoc which will calculate the area of a circle, given a radius as input. The formula for the area of a circle is πr2. We already have a way to square the radius with our squared function, so let’s just write the new function.

def aoc(radius):
  return 3.14 * squared(radius)
aoc(4)
#===> 50.240000000000002

When aoc(4) is called Python looks up the definition of aoc and replaces all occurrences of radius with the number 4. Then Python evaluates the instructions found in aoc. In the instructions Python finds a call to squared so it looks up the instructions to squared and replaces all occurrences of number with the value 4. It then evaluates the instructions in squared and returns 16. squared(4) is then replaced with 16 and Python returns 3.14 * 16 or roughly 50.24.

 

Examples of Functions in Other Languages

Javascript

function aoc(c) {
  var r = c/2;
  return 3.145*(r*r);
}
aoc(8)
//>>> 50.264

Scheme

(define (aoc c)
  (define r (/ c 2))
  (* 3.1415 (* r r)))
(aoc 8)
;>>> 50.264

 

Links

GOTO Table of Contents