Understanding Time Complexity in Sorting Algorithms
Classified in Computers
Written at on 
English with a size of 12.09 KB.
1. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case? Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
2. Suppose we have a O(n) time algorithm that finds median of an unsorted array. Now consider a QuickSort implementation where we first find median using the above algorithm, then use median as pivot. What will be the worst case time complexity of this modified QuickSort. O(nLogn)
3. Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity? Heap Sort with time complexity O(nLogk)
4. Which of the following is not true about comparison based sorting algorithms?Heap Sort is not a comparison based sorting algorithm
5. What is time complexity of fun()? O(n)
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
6. What is the time complexity of fun()? Theta (n^2)
{
int count = 0;
for (int j = i; j > 0; j--)
return count
}
f1(n) = 2^n
f2(n) = n^(3/2)
f3(n) = nLogn
f4(n) = n^(Logn)
f3, f2, f4, f1
8. What is the best time complexity of bubble sort? N
9. What is the worst case time complexity of insertion sort where position of the data to be inserted is calculated using binary search?N^2
10. What is the time complexity of the below function? O(n)
void fun(int n, int arr[])
{
int i = 0, j = 0;
for(; i < n; ++i)
while(j < n && arr[i] < arr[j])
j++;
}
11. In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops:
A) for(i = 0; i < n; i++)
B) for(i = 0; i < n; i += 2)
C) for(i = 1; i < n; i *= 2)
D) for(i = n; i > -1; i /= 2)
12. If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)? C
14. 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.
15. The recurrence equation 2n + 1- n - 2
T(1) = 1
T(n) = 2T(n - 1) + n, n ≥ 2 16. Which of the following is TRUE? The cost of searching an AVL tree is θ (log n) but that of a binary search tree is O(n)
8, 15, 20, 47, 4, 9, 30, 40, 12, 17
18. Which of the following algorithm design technique is used in finding all pairs of shortest distances in a graph?
Dynamic programming
19. What is the time complexity of following function fun()? Assume that log(x) returns log value in base 2. Θ(nLogn)
void fun()
{
int i, j;
for (i=1; i<=n; i++)
for (j=1; j<=log(i); j++)
printf("GeeksforGeeks");
}
20. Consider the program
void function(int n) {
int i, j, count=0;
for (i=n/2; i <= n; i++)
for (j = 1; j <= n; j = j*2)
count++;}
The complexity of the program is
O(n log n)
21.Which of the following points is/are true about Linked List data structure when it is compared with array
Arrays have better cache locality that can make them better in terms of performance.
It is easy to insert and delete elements in Linked List
Random access is not allowed in a typical implementation of Linked Lists
The size of array has to be pre-decided, linked lists can change their size any time.
22.Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
Merge Sort
23.In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is n
24.Consider the function f defined below.
struct item
{
int data;
struct item * next;
};
int f(struct item *p)
{
return (
(p == NULL) ||
(p->next == NULL) ||
(( P->data <= p->next->data) && f(p->next))
);
}
For a given linked list p, the function f returns 1 if and only if
the elements in the list are sorted in non-decreasing order of data value
25.//Fibonacci Series using Recursion
#include<bits/stdc++.H>
using namespace std;
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
int main ()
{
int n = 9;
cout << fib(n);
getchar();
return 0;
}
26.
27.
28.
29.
30
31.
32
33.
34.
35.
36.
37.
38.
39.
40