Ternary search

_____________________________________________________________________________
Suppose we search an array of size 26 for the «first» element in the array.

is_string_in_array("apricot", …, 26)            # calls strcmp(…) 1 time  # executes 18 lines of code
  └─ is_string_in_array("apricot", …, 9)        # calls strcmp(…) 1 time  # executes 18 lines of code
     └─ is_string_in_array("apricot", …, 3)     # calls strcmp(…) 1 time  # executes 18 lines of code
        └─ is_string_in_array("apricot", …, 1)  # calls strcmp(…) 1 time  # executes  3 lines of code

When n == 1, is_string_in_array(…) will be invoked  1 time.
When n >= 2, is_string_in_array(…) will be invoked ██ to ██ times.

_____________________________________________________________________________
Base of a log does not matter.

          log₂ n
log₃ n = ──────────
          log₂ 3

             1
log₃ n = ──────── × log₂ n
          log₂ 3



_____________________________________________________________________________
If some component of the running time varies by a factor within a constant range,
it does not affect the running time.

In this example, depending on whether n is odd or even, strcmp(…) will be called either n or 2n
times.  Either way, if f(n) is the number of times strcmp is called, f(n) is O(n).

void foo(int n) {
    for(int i = 0; i < n; i++) {
        strcmp(…);
        if(n % 2 == 0) {
            strcmp(…);
        }
    }
}

_____________________________________________________________________________
Constant coefficients do not matter.  That does not mean that constants never matter.

For example, the base of an exponential matters.

O(2^n) is not the same as O(5^n).  Those constants *do* matter.

_____________________________________________________________________________
Suppose we search an array of size 26 for a NON-EXISTANT element "zzz" in the array.  If it did
exist, it would just after the last element in the array.

is_string_in_array("apricot", …, 26)            # calls strcmp(…) 2 times # executes 20 lines of code
  └─ is_string_in_array("apricot", …, 8)        # calls strcmp(…) 2 times # executes 20 lines of code
     └─ is_string_in_array("apricot", …, 2)     # calls strcmp(…) 2 times # executes 20 lines of code
        └─ is_string_in_array("apricot", …, 0)  # calls strcmp(…) 0 times # executes  2 lines of code