Big O Time quiz

다음 함수의 Big O는? 

 

< 문제 1 > 

function logAtLeast5(n){
  for (var i = 1; i <= Math.max(5, n); i++){
        console.log(i)
    }  
}
logAtLeast5(7);

 

 

n 이 7을 넣었을 때  

 

i = 1 

1 이 7보다 작은가 

1 출력

 

1 = 2

2 가 7보다 작은가 

2 출력 

 

...

1~7까지 일일이 물어보고 출력

... 

 

n을 1,000,000 으로 입력했다면 

1부터 모두 확인 후 1,000,000까지 출력

 

Big O 는 O(n) 이다.

 

 

 

 

< 문제 2 > 

function logAtLeast5(n){
  for (var i = 1; i <= Math.min(5, n); i++){
        console.log(i)
    }  
}
logAtLeast5(7);

 

n이 높은 숫자라 하더라도 

둘 중 작은 숫자까지 이기 때문에 

이 loop은 최대 5번까지 밖에 돌지 않는다. 

 

이런 경우 Big O는 O(1)이다.

 

 

 

 

< 문제 3 > (이해 안감) 

function onlyElementsAtEvenIndex(array){
    var newArray = Array(Math.ceil(array.length / 2));
    for (var i = 0; i < array.length; i++){
        if (i % 2 === 0){
            newArray[i / 2] = array[i];
        }
    }
    return newArray;
}

 

답은 O(n)

 

 

 

< 문제 4 > 

 

function subtotals(array) {
    var subtotalArray = Array(array.length);
    for (var i = 0; i < array.length; i++) {
        var subtotal = 0;
        for (var j = 0; j <= i; j++) {
            subtotal += array[j];
        }
        subtotalArray[i] = subtotal;
    }
    return subtotalArray;
}

 

답은 O(n^2)