1 Crore+ students have signed up on EduRev. Have you? 
Consider the following Cfunction:
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:
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.
Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored either in rowmajor or columnmajor order in contiguous memory locations. The time complexity of an algorithm to compute M1 × M2 will be
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.
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
Please note that inside the else condition, f() is called first, then counter is set to 0. Consider the following cases:
The recurrence equation
T(1) = 1
T(n) = 2T(n  1) + n, n ≥ 2
evaluates to
Consider the following three claims
1. (n + k)^{m} = Θ(n^{m}), where k and m are constants
2. 2^{n + 1} = O(2^{n})
3. 2^{2n + 1} = O(2^{n})
Q. Which of these claims are correct ?
(n + k)^{m} and Θ(n^{m}) are asymptotically same as theta notation can always be written by taking the leading order term in a polynomial expression. 2^{n + 1} and O(2^{n}) are also asymptotically same as 2^{n + 1} can be written as 2 * 2^{n} and constant multiplication/addition doesn't matter in theta notation. 2^{2n + 1} and O(2^{n}) are not same as constant is in power. See Asymptotic Notations for more details.
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?
Insertion sort runs in Θ(n + f(n)) time, where f(n) denotes the number of inversion initially present in the array being sorted.
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?
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.
The increasing order of following functions in terms of asymptotic complexity is:
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.
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 n1 in worst case.
b) for subarray on right of pivot which is of size 0 in worst case.
Consider the following C function.
Q. Which one of the following most closely approximates the return value of the function fun1?
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.
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
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.
Q. The equality above remains correct if X is replace by
X = Sum of the cubes of {1, 2, 3, .. n X = n^{2} (n+1)^{2} / 4
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. BellmanFord algorithm
2. Kruskal’s algorithm
3. FloydWarshall algorithm
4. Topological sorting
A : O(m log n)
B : O(n^{3})
C : O(nm)
D : O(n + m)
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?
n^{(logba)} = n which is = n^(1.5) = O(sqrt n) then by applying case 1 of master method we get T(n) = Θ(n)
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
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 Θ(n^{2}) time
II. Bubblesort runs in Θ(n^{2}) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
I. Given an array in ascending order, Recurrence relation for total number of comparisons for quicksort will be T(n) = T(n1)+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) // InPlace 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 subarray (because given array is sorted) is added, there won't be any swap but a single comparison. In n1 passes we will be having 0 swaps and n1 comparisons. Total time complexity = O(n) // N1 Comparisons
//// For an array already sorted in ascending order, Quicksort has a complexity Θ(n^{2}) [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]
A problem in NP is NPcomplete if
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. 3SAT being an NPC problem, reducing it to a NP problem would mean that NP problem is NPC.
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
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
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
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.
000000000
Arrange the following functions in increasing asymptotic order:
A. n^{1/3}
B. e^{n}
C. n^{7/4}
D. n log^{9}n
E. 1.0000001^{n}
150 docs215 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
150 docs215 tests








