[Algorithm] what is BigO?

뱅타 2022. 2. 3. 22:30

Linear Algorithm

O(N)

O(1)

public void print_first(arr){
    System.out.println(arr[0])
}

It doesn't matter how big the input is this function will tate the same amout of steps to finish.

O(n^2)

public void print_twice(arr){
    for(int n: arr){
        for(int x: arr){
            print(x, n);
        }
    }
}

O(log n)

ex) binary search

Logarithm is the opposite of exponents.

2^n = 32

what is 'n' ?

2 * 2 * 2 * 2 * 2 = 32

n = 5

n = log2(32)

what is 'n' ?

32 / 2 = 16

16 / 2 = 8

8 / 2 = 4

4 / 2 = 2

2 / 2 = 1

So n = 5

728x90