worst-case

An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] is sorted...

$$\text { The pseudocode of a function fun( ) is given below : }$$ fun(int A[0, .., n-1]) { for i = 0 to n-2 for j=0 to n-i-2 if (A[]]>A[j + 1]) then swap A[j] and A[j+1] } Let $A[...

Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass thro...

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

What is the worst case time complexity of inserting n elements into an empty linked list, if the linked list needs to be maintained in sorted order?

There are n unsorted arrays : A 1 , A 2 , …, A n . Assume that n is odd. Each of A 1 , A 2 , …, A n contains n distinct elements. There are no common elements between any two array...

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in...

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

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n ( $$ \ge 2$$ ) numbers? In the recurrence equation...

Assume that a mergesort algorithm in the worst case takes $$30$$ seconds for an input of size $$64.$$ Which of the following most closely approximates the maximum input size of a p...

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case...

Let P be a QuickSort Program to sort numbers in ascending order using the first element as pivot. Let t 1 and t 2 be the number of comparisons made by P for the inputs {1, 2, 3, 4,...

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object in to a binary search tree of n nodes?

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty and m > 0) { Deque...

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

What is the number of swaps required to sort n elements using selection sort, in the worst case?

In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is

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?

Suppose we want to arrange the n numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot i) 1, 2, 3,......., n ii) n, n-1, n-2,......, 2, 1 Let C 1 and C 2 be the number...

Both’s algorithm for integer multiplication gives worst performance when the multiplier pattern is

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…n] are to be sorted, give an input for which Quicksort tak...

Let P be a quicksort program to sort numbers in ascending order. Let t 1 and t 2 be the time taken by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of t...