Assignment: Time & Space Complexity | DSA in C++ - Software Development PDF Download

Multiple Choice Questions (MCQs)

Q.1. Which of the following measures the efficiency of an algorithm?
(a) Time complexity
(b) Space complexity
(c) Both a and b
(d) None of the above

Ans. (c)

Q.2. Time complexity of an algorithm is usually expressed in terms of:
(a) The number of instructions executed
(b) The amount of memory used
(c) The number of comparisons made
(d) The execution time in seconds

Ans. (a)

Q.3. The time complexity of an algorithm with a loop that runs 'n' times and an inner loop that runs 'm' times is:
(a) O(n)
(b) O(m)
(c) O(n + m)
(d) O(n * m)

Ans. (d)

Q.4. The space complexity of an algorithm is determined by:
(a) The amount of memory used by the program
(b) The number of instructions executed
(c) The size of the input
(d) The execution time in seconds

Ans. (a)

Q.5. Which of the following is true about the space complexity of an algorithm?
(a) It measures the amount of disk space used by the program
(b) It measures the amount of memory used by the program
(c) It measures the time taken by the algorithm to execute
(d) It measures the number of operations performed by the algorithm

Ans. (b)

Higher Order Thinking Questions (HOTS)

Q.1. Consider the following code snippet:

void foo(int n)

{

    for (int i = 0; i < n; i++)

    {

        for (int j = 0; j < n; j++)

        {

            // Some code

        }

    }

}

(a) What is the time complexity of the function 'foo'?

Ans. O(n²)

(b) What is the space complexity of the function 'foo'?

Ans. O(1)

Q.2. Consider the following code snippet:

int bar(int n)

{

    if (n <= 0)

        return 0;

    else

        return 1 + bar(n - 1);

}

(a) What is the time complexity of the function 'bar'?

Ans. O(n)

(b) What is the space complexity of the function 'bar'?

Ans. O(n)

Q.3. Consider the following code snippet:

void baz(int n)

{

    for (int i = 0; i < n; i++)

    {

        // Some code

    }

    for (int j = 0; j < n; j++)

    {

        // Some code

    }

}

(a) What is the time complexity of the function 'baz'?

Ans. O(n)

(b) What is the space complexity of the function 'baz'?

Ans. O(1)

Q.4. Consider the following code snippet:

void qux(int n)

{

    if (n <= 0)

        return;

    else

    {

        // Some code

        qux(n / 2);

        qux(n / 2);

    }

}

(a) What is the time complexity of the function 'qux'?

Ans. O(2ⁿ)

(b) What is the space complexity of the function 'qux'?

Ans. O(n)

Q.5. Consider the following code snippet:

void quux(int n)

{

    if (n <= 0)

        return;

    else

    {

        // Some code

        quux(n - 1);

    }

}

(a) What is the time complexity of the function 'quux'?

Ans. O(n)

(b) What is the space complexity of the function 'quux'?

Ans. O(n)

Fill in the Blanks

1. The _________ complexity of an algorithm is a measure of the amount of time taken by an algorithm to run as a function of the length of the input.

The time complexity of an algorithm is a measure of the amount of time taken by an algorithm to run as a function of the length of the input.

2. The _________ complexity of an algorithm is a measure of the amount of memory used by an algorithm to run as a function of the length of the input.

The space complexity of an algorithm is a measure of the amount of memory used by an algorithm to run as a function of the length of the input.

3. The time complexity of an algorithm is usually expressed using _________ notation.

The time complexity of an algorithm is usually expressed using Big O notation.

4. The space complexity of an algorithm is usually expressed using _________ notation.

The space complexity of an algorithm is usually expressed using Big O notation.

5. The worst-case time complexity of an algorithm represents the _________ amount of time required for any input of size 'n'.

The worst-case time complexity of an algorithm represents the maximum amount of time required for any input of size 'n'.

True or False

1. The time complexity of an algorithm measures the amount of memory used by the program.

False

2. The space complexity of an algorithm measures the number of operations performed by the algorithm.

False

3. The time complexity of an algorithm is independent of the input size.

False

4. The space complexity of an algorithm can never exceed its time complexity.

False

5. The best-case time complexity of an algorithm represents the maximum amount of time required for any input of size 'n'.

False

Hands-On Questions

Q.1. Write a C++ function sumOfArray that takes an array of integers and its size as input and returns the sum of all the elements in the array. Analyze the time and space complexity of the function.

Time complexity: O(n), Space complexity: O(1)

Q.2. Write a C++ function isPrime that takes an integer as input and returns true if the number is prime, and false otherwise. Analyze the time and space complexity of the function.

Time complexity: O(sqrt(n)), Space complexity: O(1)

Q.3. Write a C++ function fibonacci that takes an integer 'n' as input and returns the 'n'th number in the Fibonacci sequence. Analyze the time and space complexity of the function.

Time complexity: O(2ⁿ), Space complexity: O(n)

Q.4. Write a C++ function binarySearch that takes a sorted array of integers, its size, and a target element as input and returns the index of the target element in the array (or -1 if it's not present). Analyze the time and space complexity of the function.

Time complexity: O(log n), Space complexity: O(1)

Q.5. Write a C++ function selectionSort that takes an array of integers and its size as input and sorts the array using the selection sort algorithm. Analyze the time and space complexity of the function.

Time complexity: O(n²), Space complexity: O(1)