[UJAD] Big O Notation

🚨 이 글은 'Colt Steele'의 'JavaScript 알고리즘 & 자료구조 마스터클래스' 강의를 듣고 정리한 글입니다.
https://www.udemy.com/course/best-javascript-data-structures/?couponCode=BFCPSALE24

What is Big O?

We have multiple implementations of the same function.

How can we determine which one is best?

Who Cares?

• for technical interview, code competition
• to discuss trade-offs between different approaches
• make us to know what slows down the code

---

Timing out the code

What does "better" mean?

• faster?
• less memory-intensive?
• more readable

Problem with time

• Different machines will record different times
  • even same machine can record differently

---

Counting number of simple operations

only care about "trends"

---

Big O Definition

We say that 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) = f of n

• f(n) could be linear (f(n) = n)
• f(n) could be quadrantic (f(n) = n^2)
• f(n) could be constant (f(n) = 1)
• f(n) could be something entirely different

---

Big O Shorthands

1. Arithmetic operations are constant
2. Variable assignment is constant
3. Accessing elements in an array(by index) or object(by key) is constant
4. In a loop, the complexity is the length of the loop times the complexity of whatever happens inside of the loop

---

Quiz

Time Complexity

1)

function logUpTo(n) {
    for (var i = 1; i <= n; i++) {
        console.log(i);
    }
}

2)

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

3)

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

4)

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;
}

5)

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;
}

---

Space Complexity

how much additional memory do we need to allocate in order to run the code in our algorithm?

about Inputs?

Sometimes you'll hear the term auxiliary space complexity to refer to space required by the algorithm, not including space taken up by the inputs.

Unless otherwise noted, when we talk about space complexity, technically we'll be talking about auxiliary space complexity.

Space complexity in JS Rules of Thumb

• Most primitives(booleans, numbers, undefined, null) are constant space
• Strings require O(n) space(where n is the string length)
• Reference types are generally O(n), where n is the length (for arrays) or the number of keys(for objects)

Example

---

Quiz

Space complexity

1)

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

2)

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

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;
}

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;
}

---

Logarithms

what is a log?

💡 log === log_2

Logarithms Rules of thumb

The logarithm of a number roughly measures the number of times you can divide that number by 2 before you get a value that's less than or equal to one

Who Cares?

Certain searching algorithms have logarithmic time complexity.

Efficient sorting algorithms involve log.

Recursion sometimes involves lg space complexity.