Log N Runtimes

[!INFO]-
topic: 🖥️ Tech
links: Big O Notation
source: Cracking the Coding Interview
tags: #permanent-note #published

Last Modified: =dateformat(this.file.mtime, "MMM. dd, yyyy - HH:mm")

O(log N) describes an algorithm that halves N after each run, e.g. A binary search.

If you have a logarithmic runtime, this describes that the number of repetitions is halved after each run. A good example is a binary search.

A sorted array of elements is halved each time depending on a condition. This is a good indicator for O(log N).