DON'T Trust Big O Notation

You've probably come across the Big O notation at some point. It is a measure to describe how a function scales and computer scientists use it to classify the execution time of algorithms. And oh boy, does that come with some problems. Which we talk about in this video. Hope you enjoy!

--

Follow us on twitter to stay updated on Furcifer news and tutorials:

[PlayWithFurcifer]

Hey guys, hope you liked the video! Should we make more videos about computer science oddities?

[KyleLuce]

These are good points on understanding bounds and run time growth not always following expected patterns.

Beyond the theory, I think it's a good example of why pragmatic performance testing is a good idea, on anything critical.

[meandersson]

I understood some of the words used in this video!

On a serious note, this is very useful because it's one of those things that pop up every now and then as I continue my learning (on my own :). Good to have some clarification.
Wouldn't mind more videos like this.

[mmxgn]

A funny recent example of this is that I came across (like you learn in an algorithms course) of matrix multiplication. The "normal" way of doing it is in O(n^3) but there are other algorithms which are "asymptotically faster" but are impractical for use (e.g. the algorithm by Coppersmith and Winograd which is in O(n^2.37) time but it's only faster for matrices so large they cannot fit in memory.)

[PBOZAI]

As a graduate applied mathemetician I can confirm the dirty theorists don’t care about anyone but themselves.

[ShoTro]

As a developer with a computer science degree who deals with other developers with computer science degrees... My response to O notation is usually pointing to the performance graph. I don't care about O notation I only care what creates there best performance within the security requirements. Taking about O notation is not helpful if there isn't a performant solution available.

[tendocat]

This one was interesting. I always thought that way. Big O is a used to simplify and it is still a good thing to know than 2^n or n! problems are impossible. Upper, lower and median values should be considered too.

That's a pity that we don't talk too much about the data at University (I'm ending my master)

[sempersolus]

I heard that mergeSort is impractical for sorting smaller lists, despite being in O(nlogn). I guess this is why.

[Ikuti]

Very cool video, it's good to see topic I learned in university in the wild :D Would be happy to watch more of these.

[Ash_]

Big O notation is good for one thing only: making certain developers feel smugly superior thinking they understand it more correctly than another developer. As a computer science graduate I studied it 25 years ago and have found it almost entirely useless ever since. Instead, as a career software developer, I've just focused on practical, pragmatic, real world concerns.

I think about the answers to questions such as what is the upper limit of the size of the data you need to handle? What is the typical size of that data? What available data structures and algorithms does my framework/engine provide? What are the trade offs each of those makes regarding execution/memory performance? Do I actually need to keep everything in memory for max performance or can I use the disk as a cache? How often will I need to execute that algorithm, e.g. once at startup, or at 60 Hz in a game loop? Is writing understandable/maintainable code to process a million elements that takes 10 times as long compared to optimized/complicated code really "worse", if that code runs once a day?

Probably its only use is as a quick indicator of the rough performance of an algorithm/structure in documentation. eg. when docs say "retrieval of an item by value is close to O(1) " I am reasonably confident that this is the hash table / dictionary implementation and what it is relatively good at (retrieval) and relatively not good at (sorted iteration).

[flamelizard]

Very nice explanation and video 😁 I hope to see more of this in the future! And yes we Germans do love Ordnung, don’t we?😂

[parvonik]

it does have practical applications, not so much in video games but more in government facilities or military applications where those milliseconds really do matter.
youre correct in that it does not reveal everything, and that is exactly why we also use means or amortized complexity that try to paint what an actual average case would look like.

[lkasikakalus]

dam cool, i watch it from start to finish. and i know nothing about big O. first time i guess

[tuhkiscgibin]

Just got out of Germany. Hope don't have to eat there again.

Anyway a really good and interesting video. Haven't studiet computer science, but mostly understood everything. Good work in explaining!

[GameDevJourney]

I laughed so hard at the German Pride bit! Also, very proud of myself for convincing myself that I understood any of that.

[fcktyshawn]

could you guys make a tutorial breaking down godots ui system?

[maymayman]

I love big theta, thank you for this excellent video

[KlausWulfenbach]

I'll tell you what Big O is good for: leaving the viewer with cliffhangers at the end of each season that will never be properly explained. 🤔

[auroraRealms]

The only time I have found "Big O" useful in Godot is in shaders, and particles. Just be mindful of how many particles are being projected onto the screen at one time. Also, I would think that shaders perform much better than particles, if implemented properly. The other place "Big O" is useful (not in game programming) is database access, on large data sets. In which case properly placed indexes eradicate performance problems. In short "Big O" is not useful unless performance problems crop up. Then it is useful when looking to see if there are nested loops in the code, or if something behind the scenes is producing an exponential large amount of data.

[whoisthis]

won a sub here. you are awesome guys, cover more topics on computer science, maybe in the context of gamedev, since this is your primary audience. Greetings from Ukraine ^_^