# Algorithms – Complexity

January 11, 2010 2 Comments

# Complexity

Note: You *really* need to read the algorithms text book chapters 1 to 3 as well as reading these notes!

Second note: This will probably be quite short as I’m cutting out all the exposition from the notes and just including the important information.

## Analysing Algorithms

For any algorithm we are analysing 2 main things:

- Correctness
- and Complexity

Complexity is about the resources that the algorithm is using. There are 2 resources is might use, those are:

- Time (Run time)
- Space (How much memory does it use)

Run time is important because some things can’t be delayed, eg software for a fighter jet.

Run time depends heavily on the input, but not just it’s size. Normally a larger input = larger run time.

The thing that matters most is **rate of growth** with input size.

## Functions and Big O

We often write algorithms as functions. For example we might say that algorithm A is *f(n) = 2n*.

Now let’s say we have 2 functions:

*f(n) = 10n**g(n) = 20n*

In Big O notation these are the same, as they both have the same order (power of n). So we can write both functions in Big O notation as *O(n)*.

If we had *h(n) = 2n²*, in Big O notation that would be* O(n²)*.

If you plot different functions onto a graph you’ll be able to see which functions are the fastest by looking at how fast they grow.

For example, for *f(n) = 10n*, with an input of 50, the function would return 500. Putting 50 into* h(n) – 2n²* would return 5000.

## Growth Rates in Order

- log n (slowest growth rate)
- √n
- n
- n²
- 2^n
- n! (highest growth rate)

The last 2 are said to be intractable, meaning that they normally have extremely large run times. As in ‘longer-than-the-age-of-the-universe’ run times.

## Simplifying Big O

The rule is: Find the fastest growing term and write it in it’s simplest form.

So, *O(5n³ + log n) *becomes *O(n³)*.

That’s all for the first set of notes. I think there’s about 6 in total.

Hello, what text book are you using?

The text book used would have been: “Algorithm Design: Foundations, Analysis and Internet Examples” by Michael T. Goodrich and Roberto Tamassia.