Grokking Algorithm Complexity and Big-O
Ask Author
Back to course home

0% completed

Vote For New Content
Quiz
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Question 1
Which of the following statements is true about time complexity analysis?
A
Time complexity is a measure of the number of operations an algorithm performs relative to the input size.
B
Time complexity helps measure the space used by an algorithm.
C
Time complexity analysis is not useful for comparing algorithms.
D
Time complexity is independent of the input size.
Question 2
What is the time complexity of the following code?
public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {  // Loop 1
        for (int j = i + 1; j < arr.length; j++) {  // Loop 2
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}
A
O(n)
B
O(n2)
C
O(log n)
D
O(n3)
Question 3
What is the time complexity of the following code snippet?
public void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
    for (int i = arr.length - 1; i >= 0; i--) {
        System.out.println(arr[i]);
    }
}
A
O(n)
B
O(n2)
C
O(log n)
D
O(1)
Question 4
Which of the following best describes Big-O notation?
A
It gives the exact runtime of an algorithm.
B
It measures the algorithm's best-case scenario.
C
It provides the upper bound of an algorithm's growth rate.
D
It is used for measuring space complexity only.
Question 5
Analyze the time complexity of the following code:
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}
A
O(n)
B
O(n2)
C
O(log n)
D
O(n log n)
Question 6
What is the time complexity of the following code snippet?
public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}
A
O(n)
B
O(n log n)
C
O(2n)
D
O(n2)
Question 7
What is the time complexity of the following code?
public int matrixChainOrder(int[] p) {
    int n = p.length;
    int[][] dp = new int[n][n];

    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k <= j - 1; k++) {
                int q = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j];
                dp[i][j] = Math.min(dp[i][j], q);
            }
        }
    }
    return dp[1][n - 1];
}
A
O(n)
B
O(n2)
C
O(n3)
D
O(2n)
Question 8
What is the time complexity of the following code?
public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;

    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}
A
O(n)
B
O(n2)
C
O(n log n)
D
O(2n)
Question 9
Analyze the time complexity of the following code:
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}
A
O(n)
B
O(amount * coins.length)
C
O(n2)
D
O(2n)

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible