Explain Big-O with examples, beginners guide.

Overview

Big-O notation is used to describe the Time Complexity(performance) and Space-Complexity(memory cost) of our programs. Think of each block of code as a task for your computer.

We can use Big-O to evaluate each task with a notation. Much like a grading system for your code. A++, A, B , C etc. Big-O uses notations such as O(1), O(n), o(n²) etc.

Constant Time - complexity O(1) - Grade: A++

When increasing or decreasing the value of the input has no impact on the output speed, Big-O uses complexity O(1) to describe the constant runtime, because this block of code always takes one execution step to complete. O(1) is A++. Example:

Note:

Even though the second example has multiple lines of code, but each blocks still has constant runtime. Therefore, unless the complexity changes, Big-O will keep it simple and call this method's complexity O(1), because Big-O only cares about complexity, not the number of lines of code.

Linear Time - complexity O(n) - Grade: A

O(n) is typically used to describe single loops operation. if input is the items I need to print out. Having 10 items means the loop will take 10 steps to print all; 100 items will require 100 steps in the loop. The computer needs to complete one task before moving to the next one, consider a loop is a single task. The complexity of this is linear O(n).

Note:

Notice in the above example, there are two loops, but they are not nested, there are two tasks here. Each loop is considered O(n), therefore the complexity of the method is still O(n).

Square Time - O(n²) - Grade: B

O(n²) is typically used to describe nested loops. Any nested loops is just one single task. If 3 loops are nested, the complexity would be O(n^3) and so on.

Final Thoughts

Big-O is mainly used to describe data structures and algorithms. Other Big-O notations such as O(2^n) is used to describe recursive calculation of Fibonacci numbers. O(log N) is used to describe binary search.

Big-O also uses the same notations to describe space complexity. Instead of determining performance, space complexity focuses on how many times does your program allocates memory, such as create array, hash, variable etc.

If a method uses a loop to just print 10 strings, the time complexity is O(n), but the space complexity is O(1) constant, because no memories were allocated.