**same Big-O**, tackling the same problem, and all things similar may have

**vastly different performance**.

Consider for example a "unique string" algorithm, where you want to check if a string contains all unique characters. A naive approach to the problem,

*which does not use extra data structures*, is to go through the string, iterating each letter against the entire string searching for a match. This approach is

**O(n^2)**.

int strunique_naive(const char *str) { char *iter, *tmp; for (iter = (char *)str; *iter != '\0'; ++iter) for (tmp = (char *)str; *tmp != '\0'; ++tmp) if (*tmp == *iter) return 0; return 1; }

Now consider a better approach to the problem. We can optimize the algorithm by adding an offset for the iterating over the string part, since for example in a short string there is no reason to test the last character with the first character as the first character already performed that test during its loop-through.

int strunique_better(const char *str) { size_t offset = 0; /* offset at 0 */ char *iter, *tmp; for (iter = (char *)str; *iter != '\0'; ++iter, ++offset) for (tmp = (char *)str + offset; *tmp != '\0'; ++tmp) if (*tmp == *iter) return 0; return 1; } int strunique_best(const char *str) { size_t offset = 1; /* pre-emptively shift offset up */ /* repeat code above */ }

When we calculate the number of loops for the worst-case scenario (i.e. a string that is unique) for the naive algorithm, we get

**n^2**loops. The better algorithm is done in

**(n^2 + n) / 2**, and the best is

**n * (n - 1) / 2**loops. The following table shows the differences:

### # of Loops on Worst Case

strunique_naive | strunique_better | strunique_best | |
---|---|---|---|

1 character | 1 | 1 | 0 |

2 characters | 4 | 3 | 1 |

3 characters | 9 | 6 | 3 |

5 characters | 25 | 15 | 10 |

10 characters | 100 | 55 | 45 |

100 characters | 10,000 | 5,050 | 4,950 |

So why can you not trust Big-O complexity for actual performance? All 3 algorithms are actually

**O(n^2)**! The better and best algorithms just have an improved actual performance equation.

### Algorithm Benchmarks

strunique_naive | strunique_better | strunique_best | |
---|---|---|---|

Big-O Complexity | O(n^2) | O(n^2) | O(n^2) |

Actual Performance | n^2 | (n^2 + n) / 2 | n * (n - 1) / 2 |