Skip to content

Define

We use Big O to express the growing of total Program Instruction need to be done for a algorithm base on it’s input.

Key point:

  • The total count of input is call n
  • Big O specifically ignore/drop any constant.

Detecting

It not a fully clear, but we can focus on loop appearance in the algorithm.

A example of O(n):

arr = [1, 23, 5, 7, 8, 8, 9, 25, 3, 423, 43, 25, 4, 36, 56, 7, 525, 68,  44, 7, 8, 9, 8, 9, 809, 233, 445, 6, 34, 6]
n = len(arr)
sum = 0
for i in range(n):
   sum += arr[i]
print(sum)

We can use a best case and worst case (or even average case) if the loop can be logically end before hand. But we mostly want to use worst case to represent the algorithm.

Example with problem:

Last update : October 13, 2023
Created : August 28, 2023