Big O Notation

Big O Notation 

 

a numeric representation of the performance of code. 

It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow. 

We won't care about the details, only the trends 

 

 

Big O Definition 

an algorithm is O(f(n)) 

if the number of simple operations the computer has to do is

eventually less than a constant times f(n), as n increases. 

 

 

f(n) could be liner ( f(n) = n )

f(n) could be quadratic ( f(n) = n^2 )

f(n) could be liner ( f(n) = 1 )

f(n) could be something entirely different 

 

 

 

 

solution 2번

O(1)

 

 

 

solution 1번 

 

5n + 2 --> n 

Number of operations is (eventually) bounded by a multiple of n. 

O(n) 

 

 

 

 

countUpAndDown(n) 함수 

 

 

O(2n)이지만 O(n)과 같다. 

 

 

 

 

Nested loops 함수 

O(n * n)