Big O - O(log(n)) code example

Question

Like the Big O notation "O(1)" can describe following code:

O(1):      for (int i = 0; i < 10; i++) {         // do stuff          a[i] = INT;     }  O(n):      for (int i = 0; i < n; i++) {         // do stuff          a[i] = INT;     }  O(n^2):     for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) {             // do stuff             a[i][j] = INT;         }     } 

• What code can O(log(n)) describe?

Another question:

• What solutions are there for "Big O problems" (what to do, when getting a lot of data as an input)?

Answer 1

Classic example:

while (x > 0) {      x /= 2;   }   

This will be:

Iteration |   x ----------+-------     0     |   x     1     |  x/2     2     |  x/4    ...    |  ...    ...    |  ...     k     |  x/2^k  

2^k = x → Applying log to both sides → k = log(x)