JS / 시간 복잡도를 빅오 표기법으로 바꾸기

// 1. 주어진 연도가 윤년인지 아닌지를 확인
// 함수에 전달된 년도를 N, 년도가 몇이든 알고리즘에 걸리는 단계수는 일정함으로 O(1)
const isLeapYear = (year) => {
    return (year % 100 === 0) ? (year % 400 === 0) : (year % 4 === 0);
}

// 2. 배열의 합을 계산하는 함수
// 배열에 원소가 N개일 때 루프는 N번 실행됨으로 O(N)
const arraySum = (array) => {
    let sum = 0;
    for (let i = 0; i < array.length; i++) {
        sum += array[i];
    }
    return sum;
}

// 3. 주어진 곡물 수에 대해 체스판의 공간을 계산하는 함수
// 곡물 수에 대한 이진 탐색이 이루어진다.
// N이 두배 늘어날 때마다 루프를 한 번 더 실행함으로 시간 복잡도는 O(log n)
const chessboardSpace = (numberOfGrains) => {
    let chessboardSpaces = 1;
    let placedGrains = 1;

    while (placedGrains < numberOfGrains) {
        placedGrains *= 2;
        chessboardSpaces += 1;
    }
    return chessboardSpaces;
}

// 4. 배열에서 "a"로 시작하는 문자열만 선택하는 함수
// N은 배열 내 문자열 개수이고 배열의 길이에 비례하여 반복문이 실행됨으로 O(N)
const selectAStrings = (array) => {
    let newArray = [];

    for (let i = 0; i < array.length; i++) {
        if (array[i].startsWith("a")) {
            newArray.push(array[i]);
        }
    }
    return newArray;
}

// 5. 배열을 정렬하고, 중간값을 계산하는 함수
// 배열의 크기 N이 얼마든 알고리즘에는 정해진 단계 수만큼 걸림으로 O(1)
const median = (array) => {
    const middle = Math.floor(array.length / 2);

    if (array.length % 2 === 0) {
        return (array[middle - 1] + array[middle]) / 2;
    } else {
        return array[middle];
    }
}