Jun 19
How to start using Big(O) to understand Algorithms
src/bigO.c
We’ve all heard of Big(O). It’s something most of us learn in college and promptly forget. We also know it’s something that Top Coders and Googlers are good at and many of us would like to be good at it too! I can relate – I find many algorithms fascinating and many more intimidating. And for a long time I struggled to get my head around the concept of Big(O). I knew what it was – vaguely – but I had no deep understanding – no intuition for it at all. And I knew that it was important in telling me which algorithms were good and which weren't. If you can relate to that feeling then this article is for you – you will be able to understand Big(O) and have the beginnings of an intuition about it. As always, this blog post is also a fully executable program - this time you can use it to play with the various Big(O) algorithms and develop a feel for how they react to different inputs.
What is Big(O) anyway?
So what is Big(O)? The easiest way to understand it is - Big(O) just describes how any algorithm scales up. How does it do this? It simply focuses on the upper-limit on the algorithm ignoring all exceptions, special cases, and complex details and irrelevant constants. So when you want to know how a bit of code is going to handle more and more inputs - just figure out it's Big(O).
How do we find the Big(O)?
Finding the Big(O) is surprisingly easy! Just "squint" at your algorithm - ignore the details - find the main repetitions (the loops/recursions) and you've trapped the Big(O). Let's try it out: Example 1: ---------- for(item in haystack) { if(item == needle) return item; } Here is a simple loop that walks through every single input once. Therefore for `n` inputs it performs `n` repetitions giving us: O(n) Example 2: ---------- low = 0; high = sortedhaystack.size - 1; while(low <= high) { mid = (low+high)/2; item = sortedhaystack[mid]; if(item == needle) return item; if(item < needle) low = mid+1; else high = mid - 1; } Squinting at this algorithm we see: ... while(low <= high) { ... mid = (low+high)/2; if() low = mid; else high= mid; ... } We again start of with the entire range of inputs but each repetition halves the range it has to travel by narrowing to the mid point. This kind of discarding half a range is terribly common and terribly useful. Such a constant halving means that each repetition shrinks to log(n) items. Therefore we say this algorithm has: O(log(n)) Because this is common it is useful to keep in mind the relation between discarding chunks of input and log(n).
Why does this matter?
So now we've found the Big(O)! Big deal! How does that help us know which algorithm is better? Well remember, Big(O) gives us useful information as the algorithm scales. If we have a small haystack then it really doesn’t matter – even if each loop takes a second then a haystack of a few hundred items will finish quickly enough in both cases. But if we have a million items things get interesting: Algorithm 1: (1 second per loop) O(n) = O(1,000,000) ~> 1,000,000 seconds = 11 days to complete Algorithm 2: (1 second per loop) O(log(n)) = O(log(1,000,000)) = O(19.93) ~> 19.93 seconds = 20 seconds to complete We can now see there is a phenomenal difference between the two. Just knowing the Big(O) can really help us!
Meet the Big(O) classes
What really makes Big(O) useful is that most algorithms fall within a few Big(O) clases. Once we know them and how they scale, we can quickly estimate how almost any algorithm scales. Let's look at the important Big(O) classes now.
Taking each in turn, let's look at the important characteristics and try and build an inutition for each along with an actual working algorithm below:
/* (Some setup) */ #include<stdio.h> #include<stdlib.h> #include<time.h> #include<math.h> enum OClass { O1, O_logn, O_sqrtn, O_n, O_nlogn, O_n_power_2, O_2_power_n, O_n_permut, O_n_power_n, }; #define UNUSED(x) (void)(x) #ifdef DUMP_RESULT #define RESULT(x) printf("%s\n",#x) #else static long _dummy; #define RESULT(x) (_dummy=1) #endif /* The environment ties * the algorithms, their * descriptions, and their data. */ typedef void (*func)(void* data); struct environment { long n; func algo; void *data; enum OClass oclass; }; struct array { long sz; int *vals; }; struct search { int needle; struct array *haystack; }; struct range_sum { long *slice_sum; long root_sz; long from; long to; struct array *array; }; O(1): Flash - The Fastest O This is the Holy Grail - an algorithm that always completes in a fixed time irrespective of the size of the input. Completes 1 Million items in: 1 second . Examples: return the head of a list, insert a node into a linked list, pushing/popping a stack, inserting/removing from a queue, deleting from a doubly-linked list,...
void get_first(struct array* array) { if(array->sz > 0) RESULT(array->vals); else RESULT(-1); } O(log(n)): Shrinking Violet - Divide and Conquer These algorithms never have to look at all the input. They often halve inputs at each stage and thus have inverse the performance of the higher powers (see the Power-Sisters to contrast). Completes 1 Million items in: 20 seconds . Examples: looking up a number in a phone book, looking up a word in a dictionary, doing a binary search, find element in a binary search tree,...
void binary_jump_search(struct search *s) { long jump = s->haystack->sz / 2; long pos = 0; while(jump > 0) { while(pos + jump < s->haystack->sz && s->haystack->vals[pos+jump] <= s->needle) pos+=jump; jump = jump / 2; } if(s->haystack->vals[pos] == s->needle) RESULT("Found needle!"); else RESULT("Needle not found!"); } O(√n): Groot - The Rare O If we notice: n sqrt(n) = --------- sqrt(n) in some sense, √n is in the "middle" of `n`. This type of algorithm is not very commonly found. Completes 1 Million items in: 16 minutes . Examples: Grover’s algorithm, the square root trick
void range_sum_query(struct range_sum* rs) { long sum = 0; int i = rs->from; while((i+1)%rs->root_sz != 0 && i <= rs->to) { sum += rs->array->vals[i++]; } while(i + rs->root_sz <= rs->to) { sum += rs->slice_sum[i/rs->root_sz]; i += rs->root_sz; } while(i <= rs->to) { sum += rs->array->vals[i++]; } RESULT(sum); } void setup_slice_sums(struct range_sum* rs) { int i; rs->root_sz = (long)sqrt(rs->array->sz); int max_slice = rs->array->sz/rs->root_sz; int num_slices = max_slice + 1; rs->slice_sum = malloc(sizeof(long)*num_slices); for(i = 0;i < num_slices;i++) { rs->slice_sum[i] = 0; } for(i = 0;i < rs->array->sz;i++) { rs->slice_sum[i/rs->root_sz] += rs->array->vals[i]; } } O(n): Clark Kent - Just a Straight guy These are linear algorithms which scale directly proportional to the input. This is commonly the case because we often have to access an item at least once. Completes 1 Million items in: 11 days . Examples: finding the maximum/minimum of a collection, finding the max sequential sum, traversing a linked list, deleting from a singly-linked list,...
void linear_search(struct search *s) { int i; for(i = 0;i < s->haystack->sz;i++) { if(s->haystack->vals[i] == s->needle) { RESULT("Found needle!"); return; } } RESULT("Needle Not Found!"); } O(nlog(n)): Hisoka - Sorting Cards Sorting is pretty useful for many, many, things. When sorting we need to compare each of the items with each other. The cleverest sorting algorithms compare each item with an ever reducing set of other items and are therefore O( n log(n) ) ^ ^ | L with a reducing(log!) Compare set each item It can be shown that algorithms that need to compare elements cannot sort faster than this (Algorithms like counting sort and radix sort use other information and can be faster). Completes 1 Million items in: ~ 1 year! . Examples: Merge Sort, Quick Sort, Heap Sort...
long partition_1(int* array, long low, long high) { long left = low; long right = high; long pivot = array[low]; while(left < right) { while(array[left] <= pivot && left <= high) left++; while(array[right] > pivot) right--; if(left < right) { int tmp; tmp = array[left]; array[left] = array[right]; array[right] = tmp; } } array[low] = array[right]; array[right] = pivot; return right; } void quick_sort_1(int* array, long low, long high) { long pivot; if(low < high) { pivot = partition_1(array, low, high); quick_sort_1(array, low, pivot-1); quick_sort_1(array, pivot+1, high); } } void quick_sort(struct array *array) { quick_sort_1(array->vals, 0, array->sz-1); } O(n^2),O(n^3): The Power Sister - Growing Polynomially These algorithms grow as a polynomial of the input. O(n^2) are known as Quadratic and are known as Cubic algorithms. Higher powers are just known as bad algorithms :-) The powers usually reflect the number of nested loops in the system. Completes 1 Million items in: O(n^2) ~> 32,000 years O(n^3) ~> 32,000,000,000 years . NB: This brings up a VERY important point about Big(O) - whenever there are multiple Big-O’s in an algorithm, the biggest class wins out because it dominates the scaling. We can see this by noticing the time that smaller classes take in comparison with larger classes we have seen so far. Examples: O(n^2) - multiplying two n-digit numbers by a simple algorithm, adding two n×n matrices, bubble sort, insertion sort, number of handshakes in a room,... O(n^3) - multiplying two n×n matrices by a naive algorithm,...
void find_max_seq_sum(struct array* array) { double max_sum = 0; int i,j; for(i = 0;i < array->sz;i++) { double curr_sum = 0; for(j = i;j < array->sz;j++) { curr_sum += array->vals[j]; if(curr_sum > max_sum) max_sum = curr_sum; } } RESULT(max_sum); } O(2^n): Wonder Woman - Combination Loops These are exponential algorithms whose growth doubles with every new addition to the input. You can recognize these as recursive algorithms that solve a problem of size `n` by recursively solving two problems of size `n-1`. Another such type is one that iterates over all subsets of a set. If you find it hard to understand how iterating over subsets translates to, imagine a set of switches, each of them corresponding to one element of a set. Now, each of the switches can be turned on or off. Think of "on" as being in the subset and "off" being not included. Now it should be obvious that there are combinations. Completes 1 Million items in: 3.2x10^301019 Millennia!! . Examples: Tower of Hanoi, Naive Finonacci Calculation,...
void solve_hanoi_1(long num, int from_peg, int to_peg, int spare_peg) { if(num < 1) return; if(num > 1) solve_hanoi_1(num-1, from_peg, spare_peg, to_peg); RESULT("move remaining one from_peg -> to_peg"); if(num > 1) solve_hanoi_1(num-1, spare_peg, to_peg, from_peg); } void solve_hanoi(int num) { solve_hanoi_1(num, 1, 2, 3); } O(n!): Link - The Traveling Salesman These algorithms iterate over all possible combination of inputs. Completes 1 Million items in: 2.7x10^5565698 Millennia (good grief!!!) . Examples: The traveling salesman problem,... O(n^n): The Blackest Panther - The Slowest O This is just included for fun. Such an algorithm will not scale in any useful way and I don't know of any. Examples: Please don't find any! Did this help you understand Big-O better? Which is your favourite Big-O class? Let me know what you think!
/* (actually run algos and show results) */ char* oclass_1_str(enum OClass oclass) { switch(oclass) { case O1: return "O(1)"; case O_logn: return "O(log(n))"; case O_sqrtn: return "O(sqrt(n))"; case O_n: return "O(n)"; case O_nlogn: return "O(n log(n))"; case O_n_power_2: return "O(n^2)"; case O_2_power_n: return "O(2^n)"; case O_n_permut: return "O(n!)"; case O_n_power_n: return "O(n^n)"; default: return "ERROR!"; } } void show_time_msg_1(clock_t begin, clock_t end) { printf("%lf", (double)(end - begin)); } void show_time_taken(struct environment* environment) { clock_t begin,end; if(!environment->data) { printf("%-12s(%ld items): (Not executed)\n", oclass_1_str(environment->oclass), environment->n); return; } printf("%-12s(%ld items): ", oclass_1_str(environment->oclass), environment->n); fflush(stdout); begin = clock(); environment->algo(environment->data); end = clock(); show_time_msg_1(begin, end); printf("\n"); } /* [=] Show results of running * all algos in their * environments. */ void show_algo_results(struct environment* environments) { while(environments->algo) { show_time_taken(environments); environments++; } } /* [=] Return a large, random * array */ int* create_int_array(long sz) { long i; int *array = malloc(sz*sizeof(int)); for(i = 0;i < sz;i++) { array[i] = rand(); } return array; } /* [=] dummy function * for not implemented * algorithms. */ void do_nothing(void* data) { } /* [=] Setup the environment for * various algorithms */ struct environment* create_environments(long sz) { int i = 0; time_t t; srand((unsigned) time(&t)); /* Setup a large block of * enviroments. * NB: if the number of * algo's > 100 this should * be changed */ struct environment *environments = malloc(sizeof(struct environment)*100); struct environment *environment; /* setup data */ struct array *sorted_array = malloc(sizeof(struct array)); sorted_array->sz = sz; sorted_array->vals = create_int_array(sorted_array->sz); quick_sort(sorted_array); struct array *array = malloc(sizeof(struct array)); array->sz = sz; array->vals = create_int_array(array->sz); struct array *mutable_array = malloc(sizeof(struct array)); mutable_array->sz = sz; mutable_array->vals = create_int_array(mutable_array->sz); struct search *search = malloc(sizeof(struct search)); search->haystack = sorted_array; search->needle = sorted_array->vals[rand()%(sorted_array->sz)]; struct range_sum *rs = malloc(sizeof(struct range_sum)); rs->array = array; setup_slice_sums(rs); rs->from = rand()%(rs->array->sz); rs->to = rand()%(rs->array->sz); while(rs->from < rs->to) { rs->from = rand()%(rs->array->sz); rs->to = rand()%(rs->array->sz); } /* O(1) */ environment = &(environments[i++]); environment->n = array->sz; environment->algo = (func)&get_first; environment->data = array; environment->oclass = O1; /* O(log(n)) */ environment = &(environments[i++]); environment->n = search->haystack->sz; environment->algo = (func)&binary_jump_search; environment->data = search; environment->oclass = O_logn; /* O(sqrt(n)) */ environment = &(environments[i++]); environment->n = rs->array->sz; environment->algo = (func)&range_sum_query; environment->data = rs; environment->oclass = O_sqrtn; /* O(n) */ environment = &(environments[i++]); environment->n = search->haystack->sz; environment->algo = (func)&linear_search; environment->data = search; environment->oclass = O_n; /* O(nlog(n)) */ environment = &(environments[i++]); environment->n = mutable_array->sz; environment->algo = (func)&quick_sort; environment->data = mutable_array; environment->oclass = O_nlogn; /* O(n^2) */ environment = &(environments[i++]); environment->n = array->sz; environment->algo = (func)&find_max_seq_sum; environment->data = array; environment->oclass = O_n_power_2; /* O(2^n) */ environment = &(environments[i++]); environment->n = sz; environment->algo = (func)&solve_hanoi; environment->data = (void*)sz; environment->oclass = O_2_power_n; /* O(n!) */ environment = &(environments[i++]); environment->n = sz; environment->algo = (func)do_nothing; environment->data = NULL; environment->oclass = O_n_permut; /* O(n^n) */ environment = &(environments[i++]); environment->n = sz; environment->algo = (func)do_nothing; environment->data = NULL; environment->oclass = O_n_power_n; /* - end marker */ environment = &(environments[i++]); environment->algo = NULL; return environments; } long get_sz(int argc, char* argv[]) { if(argc < 2) return 0; return atol(argv); } int main(int argc, char* argv[]) { long sz = get_sz(argc, argv); if(!sz) printf("Usage: %s <number of items>\n", argv); else show_algo_results(create_environments(sz)); }
. . . . . . . . . .
Notify me on new blog posts
. . . . . . . . . .
says:
x² and x³ are not exponential but polynomial (quadratic and cubic respoctively). 2^n is the exponential one.
says:
Thanks Patrick. You are right. I've corrected the mistake in the blog.
says:
How is 'deleting from a doubly-linked list' O(lg n)? If you already have a pointer to the node, it's O(1). If you need to find it, it's still O(n).
says:
That's correct. Deleting from a doubly-linked list is O(1). Fixed!
says:
Is there a pdf version that I can print out?
. . . . . . . . . .