DEV Community

Discussion on: What is O(log n)? Learn Big O Logarithmic Time Complexity

Collapse
 
hpj1992 profile image
Harshit

Nice explanation.

Can you provide some other common problems which can be solved in O(logn) ?

TIA

Collapse
 
jjant profile image
Julian Antonielli

A simple example is binary searching a number in an ordered array.

Collapse
 
robconery profile image
Rob Conery • Edited

O (log n) is extremely common - and in fact the one that will save you the most time if you've ever dealt with a database slowing down. Just plopping an index on a string value will turn it from an O(n) operation (sequential scan) to an O (log n) operation - divide and conquer. Usual caveats here: databases tend to have some tweaks under the covers, but the typical index is BTREE or the like, which is O (log n).

You can quantify the time savings using the math in this post. On 1000 rows a sequential scan has to do 1000 comparisons to find the record(s) you want. With an index in place, it does log2(1000), which is ~10 (or 10 in our case). That's pretty good - and you an see why an index like that would scale really well.

In terms of algorithms you write - you'd be surprised at the optimizations you can get if you're using something like Redis, which doesn't have indexes (unless you create them). Since it's in memory though, you can scan a list for a given value using binary search - pretty damn useful :).

Collapse
 
omicron666 profile image
Omicron

O(log n) is actually not very common.
You have fast exponentiation if you wanna explore.
At best, you'll encounter O(n*log n) in general for algorithms.

Collapse
 
hpj1992 profile image
Harshit

Thanks.