What is the Big-O Complexity of This Code?

If you are struggling with Big-O Complexity (aka the Big-O Notation) this video is for you. The task is simple: read the 4 lines of code and determine their Big-O complexity. The exercise looks only at time complexity, not space complexity btw.

The exercise is more challenging than it seems at first sight. Usually, 2 for loops like these have an O(n^2) time complexity. But not in this case. The first loop multiplies by 2 in each iteration, which changes the problem completely.

The key takeaway of this video is that the complexity of an algorithm is determined by the number of instructions executed by the program, relative to the input size !!!

To measure the real complexity of this code, we will count the number of instructions executed by the program, using a mathematical proof. The techniques you’ll learn here will help you better understand Big-O complexity analysis and make you a better programmer and coder overall.

Prerequisites: (a) some basic knowledge of maths, especially sums and logarithms, and (b) at least basic programming knowledge, especially of the Big-O notation. The demonstration is done in pseudocode. JavaScript is used as well, but at a very basic level, so no knowledge of it is required.

The video was inspired by a Reddit thread that discusses the complexity of this very code: My professor just said this algorithm is O(n), theres no way, right? - https://www.reddit.com/r/algorithms/comments/j70hnj/my_professor_just_said_this_algorithm_is_on/

Enjoy! - Robert

#BigONotation #ComputerScience #NextLevelUp

Видео What is the Big-O Complexity of This Code? канала Next Level Up