I am having trouble understanding the difference between log(k) and log(n) in complexity analysis.
I have an array of size n. I have another number k < n that is an input of the algorithm (so it's not a constant known ahead of time). What are some examples of algorithms that would have log(n) vs those that would have log(k) in their complexity? I can only think of algorithms that have log(n) in their complexity.
For example, mergesort has log(n) complexity in its runtime analysis (O(nlogn)).
If your algorithm takes a list of size n and a number of magnitude k < n, the input size is on the order of n + log(k) (assuming k may be on the same asymptotic order of n). Why? k is a number represented in a place-value system (e.g., binary or decimal) and a number of magnitude k requires on the order of log k digits to represent.
Therefore, if your algorithm takes an input k and uses it in a way that requires all its digits be used or checked (e.g., equality is being checked, etc.) then the complexity of the whole algorithm is at least on the order of log k. If you do more complicated things with the number, the complexity could be even higher. For instance, if you have something like for i = 1 to k do ..., the complexity of your algorithm is at least k - maybe higher, since you're comparing to a log k-bit number k times (although i will use fewer bits than k for many/most values of i, depending on the base).
There's no "one-size-fits-all" explanation as to where an O(log k) term might come up.
You sometimes see this runtime arise in searching and sorting algorithms where you only need to rearrange some small part of the sequence. For example, the C++ standard library's std::partial_sort function, which rearranges the sequence so that the first k elements are in sorted order and the remainder are in arbitrary order in time O(n log k). One way this could be implemented is to maintain a min-heap of size at most k and do n insertions/deletions on it, which is n operations that each take time O(log k). Similarly, there's an O(n log k)-time algorithm for finding the k largest elements in a data stream, which works by maintaining a max-heap of at most k elements.
(Neither of these approaches are optimal, though - you can do a partial sort in time O(n + k log k) using a linear-time selection algorithm and can similarly find the top k elements of a data stream in O(n).)m
You also sometimes see this runtime in algorithms that involve a divide-and-conquer strategy where the size of the problem in question depends on some parameter of the input size. For example, the Kirkpatrick-Seidel algorithm for computing a convex hull does linear work per level in a recurrence, and the number of layers is O(log k), where k is the number of elements in the resulting convex hull. The total work is then O(n log k), making it an output-sensitive algorithm.
In some cases, an O(log k) term can arise because you are processing a collection of elements one digit at a time. For example, radix sort has a runtime of O(n log k) when used to sort n values that range from 0 to k, inclusive, with the log k term arising from the fact that there are O(log k) digits in the number k.
In graph algorithms, where the number of edges (m) is related to but can be independent of the number of nodes (n), you often see runtimes like O(m log n), as is the case if you implement Dijkstra's algorithm with a binary heap.
