I would like an example of an algorithm (or pseudocode) that shows $\log n$ running time. I know what $n$ and $n^k$ running time looks like (simple nested loops) but what does $\log n$ look like and what is a way to see if an algorithm is going to take $\log n$ time?
Thanks!
On
Binary search on an array is $O(\ln n)$. You start with the whole range of elements, $[0,n]$. Then you check element $\frac{n}2$ and are able to eliminate half of the elements. Each time you check the middle element of the eligible range and eliminate half of them. It takes $\log_2 n$ iterations to narrow your search down to a single element, which is $O(\ln n)$
Lots of operations on balanced tree data structures (red-black trees, AVL trees, splay trees, etc) are also $O(\ln n)$. Operations typically involve moving up and down through the nodes of the tree which has a depth guaranteed to be less than $k \ln n$, performing a limited amount of assignment and reallocation work at each node.
On
Other answers have given examples of algorithms which are $O(\log n)$ assuming that multiplication and/or comparison take constant time.
It's worth noting, however, that any significant computation will take at least $O(n)$ runtime if $n$ is assumed to be the size of the input in binary. By "significant", I mean a computation that potentially depends on the value of every bit. This is because your algorithm must at the very least read in all $n$ bits, which takes time $O(n)$.
(In particular, in the context of Turing machines, almost nothing of import has time $O(\log n)$ because the Turing machine will not be able to read in the entire string in that limited time.)
One example is computation of $a^n$ for integer $n$ which is done by successive squaring and multiplying.
This is of time $O(\ln n)$, assuming that the time for multiplying is $O(1)$.