Big-O Notation
Some common algorithms and their big-O noations
| constant time | logarithmic time | linear time | linear-multiply-log | square time | factorial time |
|---|---|---|---|---|---|
| O(1) | O(log2n) | O(n) | O(nlog2n) | O(n2) | O(n!) |
| hash | binary search | simple search | quik/merge sort | selection sort | traveling salesperson |
O(log2n)
logarithmic time
code of binary search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <stdio.h>
static int array[] = {9, 15, 21, 23, 57, 98, 101, 111};
static int asize = sizeof(array) / sizeof(int);
static void dump_array(int array[], int size, const char *prefix)
{
int i;
if (NULL != prefix) {
printf("%s: ", prefix);
}
for (i = 0; i < asize; i++) {
printf("array[%d] = %d, ", i, array[i]);
}
printf("\n");
return;
}
static int bsearch(int array[], int size, int key)
{
int i, low, high, guess;
low = 0; high = size - 1;
while (low <= high) {
guess = (low + high) / 2;
if (key > array[guess]) {
low = guess + 1;
} else if (key < array[guess]) {
high = guess - 1;
} else {
printf("key %d index is %d\n", key, guess);
return guess;
}
}
return -1;
}
int main(int argc, char *argv[])
{
int i, key[] = {0, 9, 15, 57, 98, 101, 111, 230};
dump_array(array, asize, "Array");
for (i = 0; i < sizeof(key) / sizeof(int); i++) {
if (bsearch(array, asize, key[i]) < 0) {
printf("key %d is not in array\n", key[i]);
}
}
return 0;
}
O(n)
linear time
code of simple search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50#include <stdio.h>
static int array[] = {9, 15, 21, 23, 57, 98, 101, 111};
static int asize = sizeof(array) / sizeof(int);
static void dump_array(int array[], int size, const char *prefix)
{
int i;
if (NULL != prefix) {
printf("%s: ", prefix);
}
for (i = 0; i < asize; i++) {
printf("array[%d] = %d, ", i, array[i]);
}
printf("\n");
return;
}
static int ssearch(int array[], int size, int key)
{
int i;
for (i = 0; i < size; i++) {
if (key == array[i]) {
printf("key %d index is %d\n", key, i);
return i;
}
}
return -1;
}
int main(int argc, char *argv[])
{
int i, key[] = {0, 9, 15, 57, 98, 101, 111, 230};
dump_array(array, asize, "Array");
for (i = 0; i < sizeof(key) / sizeof(int); i++) {
if (ssearch(array, asize, key[i]) < 0) {
printf("key %d is not in array\n", key[i]);
}
}
return 0;
}
O(nlog2n)
- linear-multiply-log
O(n2)
square time
code of selection sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <stdio.h>
static int array[] = {15, 9, 23, 21, 111, 101, 98};
static int asize = sizeof(array) / sizeof(int);
static void dump_array(int array[], int size, const char *prefix)
{
int i;
if (NULL != prefix) {
printf("%s: ", prefix);
}
for (i = 0; i < asize; i++) {
printf("array[%d] = %d, ", i, array[i]);
}
printf("\n");
return;
}
static void ssort(int array[], int size)
{
int i, j, hit;
for (i = 0; i < size; i++) {
hit = i;
for (j = i; j < size; j++) {
if (array[j] < array[hit]) {
hit = j;
}
}
if (i != hit) {
int swap;
swap = array[i];
array[i] = array[hit];
array[hit] = swap;
}
}
return;
}
int main(int argc, char *argv[])
{
dump_array(array, asize, "Before sort");
ssort(array, asize);
dump_array(array, asize, " After sort");
return 0;
}
O(n!)
- factorial time
Reference
Algorithms, 4th Edition
Grokking Algorithms: An illustrated guide for programmers and other curious people