The complexity class named after this function includes the undirected graph reachability problem.
The complexity class named after this function includes the undirected graph reachability problem. In terms of the number of nodes, p, this is the approximate runtime of searching, inserting and deleting an element from an AVL tree. For a height-balanced binary tree consisting of q nodes, there are approximately this function of q levels. For the average case, if there are n inputs into (*) quicksort, then the algorithm will run in n times this function of n. This is the average case runtime of the binary search algorithm, since half of the list will be removed from consideration after any given step. For 10 points, name this mathematical function, the inverse of exponentiation.
The complexity class named after this function includes the undirected graph reachability problem.
logarithm [accept "discrete logarithm"]