Big-O Notation Explained - Coding Challenges

This article, is an add-on to the first article of this series, "Understanding Big-O Notation". This is to revise what was learned/read over at the above-mentioned article.

QUESTION 1: Given the following code snippet, what is the time complexity of the getFirstElement function?

function getFirstElement(arr) {
    return arr[0];
}

A. O(n) - The time complexity grows linearly with the size of the input array.

B. O(log n) - The time complexity grows logarithmically as the size of the input array increases.

C. O(1) - The time complexity is constant, regardless of the size of the input array.

D. O(n²) - The time complexity grows quadratically as the size of the input array increases.

Given the binarySearch() function, answer the following two questions related to the binarySearch function.

QUESTION 2a: What makes the binarySearch function have an O(log n) time complexity?

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target)
            return mid;
        if (arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
}

A. It iterates through each element of the array one by one.

B. It divides the search space in half with each step, eliminating half of the remaining elements.

C. It sorts the array before searching.

D. It searches through the entire array before returning the result.

QUESTION 2b: Is the binarySearch function's space complexity the same as its time complexity? Why or why not?

A. Yes, both time and space complexities are O(log n) because the function uses a logarithmic number of recursive calls.

B. No, the time complexity is O(log n), but the space complexity is O(1) in an iterative implementation.

C. Yes, both are O(n) because the function iterates over each element of the array.

D. No, the space complexity is O(n log n) due to the repeated division of the array.

QUESTION 3: Given the following code snippet, what is the time, and space complexity of the sumArray function?

function sumArray(arr) {
    let sum = 0;
    for (let num of arr) {
        sum += num;
    }
    return sum;
}

A. Time complexity: O(1); Space complexity: O(1)

B. Time complexity: O(n); Space complexity: O(1)

C. Time complexity: O(n²); Space complexity: O(n)

D. Time complexity: O(log n); Space complexity: O(n)

QUESTION 4: Sorting algorithms like mergesort and heapsort repeatedly divide the array into smaller parts and then combine them in linear time. What will be the time complexity of such sorting algorithms?

arr.sort((a, b) => a - b);

A. O(n)

B. O(log n)

C. O(n log n)

D. O(n²)

That's it! These are just a few of the questions I have in store. More will be explored in the next two weeks. I'd like for you to answer these in the comments. If you are not sure, you can take a guess or what looks like it makes sense. The answers will be explained next week.