Logarithmic function in time complexity

Question

How does a program's worst case or average case dependent on log function? How does the base of log come in play?

Answer 1

The log factor appears when you split your problem to k parts, of size n/k each and then "recurse" (or mimic recursion) on some of them.

A simple example is the following loop:

foo(n):
  while n > 0:
     n = n/2
     print n

The above will print n, n/2, n/4, .... , 1 - and there are O(logn) such values.
the complexity of the above program is O(logn), since each printing requires constant amount of time, and number of values n will get along the way is O(logn)

If you are looking for "real life" examples, in quicksort (and for simplicity let's assume splitting to exactly two halves), you split the array of size n to two subarrays of size n/2, and then you recurse on both of them - and invoke the algorithm on each half.

This makes the complexity function of:

T(n) = 2T(n/2) + O(n)

From master theorem, this is in Theta(nlogn).

Similarly, on binary search - you split the problem to two parts, and recurse only on one of them:

T(n) = T(n/2) + 1

Which will be in Theta(logn)

---

The base is not a factor in big O complexity, because

log_k(n) = log_2(n)/log_2(k)

and log_2(k) is constant, for any constant k.