adplus-dvertising
frame-decoration

Question

The unusual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where and element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

a.

remain Θ(n^2)

b.

become Θ(n (log n)^2)

c.

become Θ(n log n)

d.

become Θ(n)

Answer: (a).remain Θ(n^2)

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. The unusual Θ(n^2) implementation of Insertion Sort to sort an array uses linear search to identify the position where and element is to be inserted into the already sorted part of...

Similar Questions

Discover Related MCQs

Q. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

Q. Which of the following statements is FALSE ?

Q. How many perfect matchings are there in a complete graph of 6 vertices ?

Q. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

-Delection of the smallest element
-Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

Q. Let S be a stack of size n ≥ 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥ 1, define the stack-life of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stack-life of an element of this stack is

Q. The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
int i = 10;
print(x + 10);
i = 200;
j = 20;
print(x);
}
main()
{
P(i + j);
}

If the programming language uses static scoping and call by need parameter passing mechanism, the values printed by the above program are

Q. The following program fragment is written in a programming language that allows variables and does not allow nested declarations of functions.

global int i = 100, j = 5;
void P(x)
{
int i = 10;
print(x + 10);
i = 200;
j = 20;
print(x);
}
main()
{
P(i + j);
}

If the programming language uses dynamic scoping and call by name parameter passing mechanism, the values printed by the above program are :

Q. Consider the following class definitions in a hypothetical Object Oriented language that supports inheritance and uses dynamic binding. The language should not be assumed to be either Java or C++, though the syntax is similar.

Class P
{
void f(int i)
{
print(i);
}
}

Class Q subclass of P
{
void f(int i)
{
print(2*i);
}
}

Now consider the following program fragment:

P x = new Q();
Q y = new Q();
P z = new Q();
x.f(1); ((P)y).f(1); z.f(1);

Here ((P)y) denotes a typecast of y to P. The output produced by executing the above program fragment will be

Q. In the following C program fragment, j, k n and TwoLog_n are interger variables, and A is an array of integers. The variable n is initialized to an integer ≥ 3, and TwoLog_n is initialized to the value of 2*⌈log2(n)⌉

for (k = 3; k < = n; k++)
A[k] = 0;
for (k = 2; k < = TwoLog_n; k++)
for (j = k + 1; j < = n; j++)
A[j] = A[j] || (j % k);
for (j = 3; j < = n; j++)
if (!A[j]) printf("%d", j);

The set of numbers printed by this program fragment is

Q. Consider the C program shown below.

#define print(x) printf("%d ", x)
int x;
void Q(int z)
{
z += x;
print(z);
}
void P(int *y)
{
int x = *y + 2;
Q(x);
*y = x - 1;
print(x);
}
main(void)
{
x = 5;
P(&x);
print(x);
}

The output of this program is

Q. The goal of structured programming is to

Q. Consider the following C function

void swap (int a, int b)
{
   int temp;
   temp = a;
   a = b;
   b = temp;
}

In order to exchange the values of two variables x and y.

Q. The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?

Q. The best data structure to check whether an arithmetic expression has balanced parentheses is a

Q. Consider the following C function:

int f(int n)
{
static int i = 1;
if (n >= 5)
return n;
n = n+i;
i++;
return f(n);
}

The value returned by f(1) is

Q. Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = D1D2…Dm

int n, rev;
rev = 0;
while (n > 0)
{
rev = rev*10 + n%10;
n = n/10;
}

The loop invariant condition at the end of the ith iteration is:

Q. Consider the following C program segment:

char p[20];
char *s = "string";
int length = strlen(s);
int i;
for (i = 0; i < length; i++)
p[i] = s[length — i];
printf("%s",p);

The output of the program is

Q. Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely ?

(i) preorder and postorder
(ii) inorder and postorder
(iii) preorder and inorder
(iv) level order and postorder

Q. 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

Q. Consider the following C program

main()
{
int x, y, m, n;
scanf ("%d %d", &x, &y);
/* Assume x > 0 and y > 0 */
m = x;
n = y;
while (m! = n)
{
if (m > n)
m = m - n;
else
n = n - m;
}
print f ("% d", n);
}

The program computes