Simplifying Big O Expressions

 

 

 

이 전 포스트에서 for loop 함수를 보면 

2n 에서 5n + 2 까지의 operations 가지는데 이것은 간단히 --> n 과 같아진다. 

몇 번의 n은 상관없이 트랜드를 보는 것이다. 

 

 

 

이렇게 알고리즘의 Time complexity를 진단할 때

Big O expressions을 위해 몇 가지 법칙이 있다. 

 

1. Constants runtime Don't Matter 

O(2n) --> O(n)

O(500) --> O(1)

O(13n^2) --> O(n^2)

 

2. Smaller Terms Don't Matter

O(n + 10) --> O(n)

O(1000000n + 50)  --> O(n)

O(n^2 + 5n + 8) --> O(n^2)

 

 

Big O Shorthands

1. Arithmetic operations ---> constant

2. Variable assignment ---> constant

3. Accessing elements in an array (by index) or object (by key) ---> constant

4. in a loop, the complexity is the length of the loop times 

the complexity of whatever happens inside of the loop ---> n^2, 3, 4...