Test: Asymptotic Worst Case Time & Space Complexity- 3

# Test: Asymptotic Worst Case Time & Space Complexity- 3

Test Description

## 20 Questions MCQ Test GATE Computer Science Engineering(CSE) 2023 Mock Test Series | Test: Asymptotic Worst Case Time & Space Complexity- 3

Test: Asymptotic Worst Case Time & Space Complexity- 3 for Computer Science Engineering (CSE) 2023 is part of GATE Computer Science Engineering(CSE) 2023 Mock Test Series preparation. The Test: Asymptotic Worst Case Time & Space Complexity- 3 questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Asymptotic Worst Case Time & Space Complexity- 3 MCQs are made for Computer Science Engineering (CSE) 2023 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Asymptotic Worst Case Time & Space Complexity- 3 below.
Solutions of Test: Asymptotic Worst Case Time & Space Complexity- 3 questions in English are available as part of our GATE Computer Science Engineering(CSE) 2023 Mock Test Series for Computer Science Engineering (CSE) & Test: Asymptotic Worst Case Time & Space Complexity- 3 solutions in Hindi for GATE Computer Science Engineering(CSE) 2023 Mock Test Series course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Asymptotic Worst Case Time & Space Complexity- 3 | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2023 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 1

### Consider the following C-function: Suppose we modify the above function foo() and store the values of foo (i), 0 < = i < n, as and when they are computed. With this modification, the time complexity for function foo() is significantly reduced. The space complexity of the modified function would be:

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 1

Space complexity now is also O(n). We would need an array of size O(n). The space required for recursive calls would be O(1) as the values would be taken from stored array rather than making function calls again and again.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 2

### Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 2

This is a trick question. Note that the questions asks about time complexity, not time taken by the program. for time complexity, it doesn't matter how we store array elements, we always need to access same number of elements of M1 and M2 to multiply the matrices. It is always constant or O(1) time to do element access in arrays, the constants may differ for different schemes, but not the time complexity.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 3

### Let A[1, ..., n] be an array storing a bit (1 or 0) at each location, and f(m) is a unction whose time complexity is θ(m). Consider the following program fragment written in a C like language: Q. The complexity of this program fragment is

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 3

Please note that inside the else condition, f() is called first, then counter is set to 0. Consider the following cases: Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 4

The recurrence equation

T(1) = 1
T(n) = 2T(n - 1) + n, n ≥ 2

evaluates to

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 4 Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 5

Consider the following three claims

1. (n + k)m = Θ(nm), where k and m are constants
2. 2n + 1 = O(2n)
3. 22n + 1 = O(2n)

Q. Which of these claims are correct ?

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 5

(n + k)m and Θ(nm) are asymptotically same as theta notation can always be written by taking the leading order term in a polynomial expression. 2n + 1 and O(2n) are also asymptotically same as 2n + 1 can be written as 2 * 2n and constant multiplication/addition doesn't matter in theta notation. 22n + 1 and O(2n) are not same as constant is in power. See Asymptotic Notations for more details.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 6

In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions?

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 6

Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversion initially present in the array being sorted.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 7

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 7

Randomized quicksort has expected time complexity as O(nLogn), but worst case time complexity remains same. In worst case the randomized function can pick the index of corner element every time.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 8

The increasing order of following functions in terms of asymptotic complexity is: Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 8 Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 9

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 9

In worst case, the chosen pivot is always placed at a corner position and recursive call is made for following.
a) for subarray on left of pivot which is of size n-1 in worst case.
b) for subarray on right of pivot which is of size 0 in worst case.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 10

Consider the following C function. Q. Which one of the following most closely approximates the return value of the function fun1?

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 10 T(n) = n(logn + loglogn) T(n) = n(logn) dominant But please note here we are return q which lies in loglogn so ans should be T(n) = nloglogn Refer this for details.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 11

An unordered list contains n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 11

We only need to consider any 3 elements and compare them. So the number of comparisons is constants, that makes time complexity as Θ(1) The catch here is, we need to return any element that is neither maximum not minimum. Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20 Pick any three elements from given liar. Let the three elements be 10, 20 and 7. Using 3 comparisons, we can find that the middle element is 10.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 12 Q. The equality above remains correct if X is replace by

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 12

X = Sum of the cubes of {1, 2, 3, .. n| X = n2 (n+1)2 / 4

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 13

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

1. Bellman-Ford algorithm
2. Kruskal’s algorithm
3. Floyd-Warshall algorithm
4. Topological sorting

A : O(m log n)
B : O(n3)
C : O(nm)
D : O(n + m)

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 13
• Bellman-Ford algorithm: Time complexity: O(VE)
• Kruskal’s algorithm:Time Complexity: O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V^2, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)
• Floyd-Warshall algorithmTime Complexity: O(V^3)
• Topological sortingTime Complexity: The above algorithm is simply DFS with an extra stack. So time complexity is same as DFS which is O(V+E).
Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 14

Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1 Which of the following statements is TRUE?

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 14

n(logba) = n which is = n^(1-.5) = O(sqrt n) then by applying case 1 of master method we get T(n) = Θ(n)

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 15

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 15
• Insertion Sort takes Θ(n2) in worst case as we need to run two loops. The outer loop is needed to one by one pick an element to be inserted at right position. Inner loop is used for two things, to find position of the element to be inserted and moving all sorted greater elements one position ahead. Therefore the worst case recursive formula is T(n) = T(n-1) + Θ(n).
• Merge Sort takes Θ(n Log n) time in all cases. We always divide array in two halves, sort the two halves and merge them. The recursive formula is T(n) = 2T(n/2) + Θ(n).
• QuickSort takes Θ(n2) in worst case. In QuickSort, we take an element as pivot and partition the array around it. In worst case, the picked element is always a corner element and recursive formula becomes T(n) = T(n-1) + Θ(n). An example scenario when worst case happens is, arrays is sorted and our code always picks a corner element as pivot.
Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 16

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE ?

I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 16

I. Given an array in ascending order, Recurrence relation for total number of comparisons for quicksort will be T(n) = T(n-1)+O(n) //partition algo will take O(n) comparisons in any case. = O(n^2)
II. Bubble Sort runs in Θ(n^2) time If an array is in ascending order, we could make a small modification in Bubble Sort Inner for loop which is responsible for bubbling the kth largest element to the end in kth iteration. Whenever there is no swap after the completion of inner for loop of bubble sort in any iteration, we can declare that array is sorted in case of Bubble Sort taking O(n) time in Best Case.
III. Merge Sort runs in Θ(n) time Merge Sort relies on Divide and Conquer paradigm to sort an array and there is no such worst or best case input for merge sort. For any sequence, Time complexity will be given by following recurrence relation, T(n) = 2T(n/2) + Θ(n) // In-Place Merge algorithm will take Θ(n) due to copying an entire array. = Θ(nlogn)
IV. Insertion sort runs in Θ(n) time Whenever a new element which will be greater than all the elements of the intermediate sorted sub-array (because given array is sorted) is added, there won't be any swap but a single comparison. In n-1 passes we will be having 0 swaps and n-1 comparisons. Total time complexity = O(n) // N-1 Comparisons

//// For an array already sorted in ascending order, Quicksort has a complexity Θ(n2) [Worst Case] Bubblesort has a complexity Θ(n) [Best Case] Mergesort has a complexity Θ(n log n) [Any Case] Insertsort has a complexity Θ(n) [Best Case]

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 17

A problem in NP is NP-complete if

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 17

A problem in NP becomes NPC if all NP problems can be reduced to it in polynomial time. This is same as reducing any of the NPC problem to it. 3-SAT being an NPC problem, reducing it to a NP problem would mean that NP problem is NPC.

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 18

The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows

a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21

A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? 110111100111010

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 18

Background Required -  Generating Prefix codes using Huffman Coding. First we apply greedy algorithm on the frequencies of the characters to generate the binary tree as shown in the Figure given below. Assigning 0 to the left edge and 1 to the right edge, prefix codes for the characters are as below. a - 1111110
b - 1111111
c - 111110
d - 11110
e - 1110
f - 110
g - 10
h - 0
Given String can be decomposed as 110 11110 0 1110 10 fdheg

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 19

What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?

Detailed Solution for Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 19

A set of vertices is called independent set such that no two vertices in the set are adjacent. A maximal independent set (MIS) is an independent set which is not subset of any other independent set. The question is about smallest MIS. We can see in below diagram, the three highlighted vertices (2nd, 5th and 8th) form a maximal independent set (not subset of any other MIS) and smallest MIS.

0----0----0----0----0----0----0----0----0

Test: Asymptotic Worst Case Time & Space Complexity- 3 - Question 20

Arrange the following functions in increasing asymptotic order:
A. n1/3
B. en
C. n7/4
D. n log9
E. 1.0000001n

## GATE Computer Science Engineering(CSE) 2023 Mock Test Series

150 docs|215 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Asymptotic Worst Case Time & Space Complexity- 3 Page
In this test you can find the Exam questions for Test: Asymptotic Worst Case Time & Space Complexity- 3 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Asymptotic Worst Case Time & Space Complexity- 3, EduRev gives you an ample number of Online tests for practice

## GATE Computer Science Engineering(CSE) 2023 Mock Test Series

150 docs|215 tests