Explain O(log n) to me

Useless shit I'll never use in life since I'm not a math or CS major.

>>8211428
that's fucking lazy of you
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00sc-introduction-to-computer-science-and-programming-spring-2011/

> CS major
> Not knowing what big O notation is
why are you even on /sci/ brainlet?

>>8211428
its kind of similar to

O(long johnson)

Let [math]f[/math] and [math]g[/math] be real functions of a real or integer variable. We say [math]f \in O(g)[/math] if there exist constants [math]c,x_0[/math] such that for all [math]x > x_0[/math], [math]\mathopen|f(x)\mathclose| \le c\cdot g(x)[/math]. Then define the plebian syntax [math]f(x) = O(g(x))[/math] to mean [math]f \in O(g)[/math].

Essentially, the growth rate of [math]f[/math] is eventually bounded by [math]g[/math]. Here, being [math]O(\log n)[/math] means you grow at most as a logarithmic function and hence e.g. you grow more slowly than any polynomial.

>>8211496
>Then define the plebian syntax
I hate that syntax too. It's commonly used by people who've never seen the proper definition and only understand it at a babby "intuitive" level.

I'm assuming you aren't asking about big-O in general, but just specifically O(log n).

Am example of O(log n) would be something like traversing a binary tree. If the tree is balanced and properly ordered, then this'll work. On the top there's one node, that's 2^0. It splits into two child nodes, that's 2^1, with the left node being less, and the right node being greater. Each of those nodes split into 2 child nodes a piece themselves, making 4, i.e. 2^2, and the pattern continues. On layer 4 you have 8 nodes, then 16, then 32, etc...

Say you're looking for a specific node in this tree: you don't have to search every node in the tree. You just have to go up and down layers, branching left if the target is smaller, and right if the target is larger, thus skipping A LOT of unnecessary steps. You could essentially search say a tree of 128 nodes in 7 steps, that's log(128)... (base 2 obviously).

>>8211428
if you're talking algorithms, it most commonly used for logarithms which cut your sample size (n) in half with every step, thus needing a total of log n steps to complete.

>>8211428
As a liberal arts student I can tell you that it looks great.
Hope that helps.

>>8211496
>>8211501
keep in mind that the definition has actually changed since its inception. "tight" $O$ was the original meaning, what we now label $Omega$.

It means that the polynomial represented has a degree of zero, but is not constant.

>>8211543
Or more intuitively, an [math]O(\log_2{n})[/math] operation is one where you can cut out half of the remaining values in every step, if you halt when there's only one remaining.