How can you tell if you an algorithm has running time of $\log n$? 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!
 A: 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.)
A: 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)$.
A: 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.
