A place for developers to talk about building on Farcaster.

/dev

Confession: I don’t know what O(n log n) means and I don’t want to.

the math notation makes it more confusing than it really is but a lot of people struggle with internalizing it. it's just an indicator of, how well your function can handle a lot of data. there are functions that are O(n3) that work fine for a small amount of data but if you put it into production with real users, it falls over instantly.

Engineering @Anchorage Digital | 

Crypto/blockchain tech enthusiast

Blockchain developer, scraping and smart contracts.

the best way is to think about it is in terms of trees in my opinion! for example a binary search is log_2(n) complexity, because you divide the search space in half recursively until you find the item.

so an nlog(n) algorithm is something that does that recursive tree splitting behavior, but does it n times. for example inserting into a balanced binary tree.

the position search takes log(n) and you insert n items, and its n * log(n)

I know that part. I don’t know how to tell if an algorithm has that complexity.

If it a tree, just say log n. When the other person says, I think it might be n log n, just look up to the right with an inquisitive, pensive look, and say you were thinking of the lower bound

Awww! Most stable sorting algorithms are O(n log n)

I.E Python and Java sort. 

The log n part is the height of each insertion/comparison level, but you do n of them.