Despite taking multiple math courses that have each explained them, and now a computer science course that requires knowledge of them, logarithms make no sense to me. Specifically their application to Big-O and complexity for computer science, like how does one make an algorithm that follows a logarithmic complexity?
In: 1
Algorithms with logarithmic complexity are ones that employ logical strategies like divide-and-conquer to remove the need to visit every element in the data you’re acting on. Most of them rely on having data pre-sorted or organized in some useful way in order to be able to ignore large parts of it.
For example, finding an element in a balanced, sorted tree: If each node in the tree has a value, a left child, and a right child, and the left child is set to always have its own value be less than the current node’s value, you can use these rules to search for any value in the tree starting from the root without needing to check every node. If the tree is balanced you visit lg(N) nodes, so this is an O(lg(N)) algorithm where N is the number of nodes.
Note that to create a sorted, balanced tree in the first place is an O(N * lg(N)) process because you need to find where to put each value. Only searching within a tree you’ve already got is logarithmic.
Latest Answers