1.Algorithm is a ________________.
Processing of problem
Step by Step method to solve a problem
Graphical method
None of the above
2.Algorithm should have _______________ or more output.
Zero
One
Two
Three
3.Which is correct according to increasing order of growth rate
n, n! , nlogn , n^2 , n^3 , n^5 , 2^n
nlogn , n^2 , n^3 , n^5 , 2^n , n!
n , nlogn , n^2 , n^3 , n^5 , 2^n , n!
n , nlogn , n^2 , n^3 , n^5 , n!, 2^n
4.Big Oh! notation looks for____________ value.
Maximum
Minimum
Average
Mean
5.Omega (Ω) notation looks for ___________ value.
Maximum
Minimum
Average
Mean
6.A function which calls itself is called __________ function.
Null
Default
Recursive
Non recursive
7. _____________ method is used to solve recurrence.
Main
Major
Divide
Master
8.Time complexity of binary search is _____________.
O(n)
O(logn)
O(nlogn)
None of the above
9.The condition for applying binary search is _______________.
Elements should be sorted
Elements should be unsorted
Elements should have priority
None of the above
10.best case of binary search, the searching element is at _______________ position.
First
Second
Last
Middle
11.The __________________of an algorithm is the amount of computer time it needs to run to completion.
Time complexity
Space complexity
Time period
None of the above
12.The minimum number of comparisons required finding the minimum and maximum of 100 numbers is ________
99
100
101
None of the above
13.Divide and Merge operation is done in ____________.
Binary search
Merge sort
Quicksort
Heap sort
14.Which sort takes an extra array.
Binary search
Merge sort
Quicksort
Heap sort
15.Recurrence equation of merge sort is _______________.
T(n) = T(n/2) + O(n)
T(n) = 2T(n/2) + O(n)
T(n) = 3T(n/2) + O(n)
None of the above
16.Pivot element is used in ___________ sort.
Binary search
Mergesort
Quick sort
Heap sort
17.Partition operation is done in _____________ sort.
Binary search
Mergesort
Quick sort
Heap sort
18.Quick sort algorithm is an example of
Greedy
Improved search
Dynamic Programming
Divide and Conquer
19.Time complexity of merge sort is ___________.
O(n)
O(logn)
O(nlogn)
None of the above
20.Time complexity of quick sort is depends on _____________.
O(n)
O(logn)
O(nlogn)
None of the above
21.Merge sort uses which of the following technique to implement sorting?
Backtracking
Greedy algorithm
Divide and conquer
Dynamic programming
22.What is the average case time complexity of merge sort ?
O(n log n)
O(n^2)
O(n^2log n)
O(n log n2)
23.What is the auxiliary space complexity of merge sort?
O(1)
O(log n)
O(n)
O(n log n)
24.Merge sort can be implemented using O(1) auxiliary space.
True
False
25.What is the worst case time complexity of merge sort?
O(n log n)
O(n^2)
O(n^2 log n)
O(n logn2 )
26.Which of the following method is used for sorting in merge sort?
Merging
Partitioning
Selection
Exchanging
27.What will be the best case time complexity of merge sort ?
O(n log n)
O(n2)
O(n2 logn)
O(n logn2)
28. Which of the following is not a variant of merge sort ?
In-place merge sort
Bottom up merge sort
Top down merge sort
Linear merge sort
29.Choose the incorrect statement about merge sort from the following?
It is a comparison based sort
It is an adaptive algorithm
It is not an in place algorithm
It is stable algorithm
30.Which of the following is not in place sorting algorithm?
Merge sort
Quick sort
Heap sort
Insertion sort
31.Which of the following is not a stable sorting algorithm?
Quick sort
Cocktail sort
Bubble sort
Merge sort
32.Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?
Quick sort
Insertion sort
Selection sort
Merge sort
33.Merge sort is preferred for arrays over linked lists.
True
False
34.Which of the following sorting algorithm makes use of merge sort?
Tim sort
Intro sort
Bogo sort
Quick sort
35.Choose the correct code for merge sort.
void merge_sort(int arr[], int left, int right) { if (left > right) { int mid = (right-left)/2; merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); merge(arr, left, mid, right); //function to merge sorted arrays } }
void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left+(right-left)/2; merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); merge(arr, left, mid, right); //function to merge sorted arrays } }
void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = left+(right-left)/2; merge(arr, left, mid, right); //function to merge sorted arrays merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); } }
void merge_sort(int arr[], int left, int right) { if (left < right) { int mid = (right-left)/2; merge(arr, left, mid, right); //function to merge sorted arrays merge_sort(arr, left, mid); merge_sort(arr, mid+1, right); } }
36. Which of the following sorting algorithm does not use recursion?
Quick sort
Merge sort
Heap sort
Bottom up merge sort
37.Which of the following sorting algorithms is the fastest ?
Merge sort
Quick sort
Insertion sort
Shell sort
38.Quick sort follows Divide-and-Conquer strategy.
True
False
39.What is the worst case time complexity of a quick sort algorithm?
O(N)
O(N log N)
O(N^2 )
O(log N)
40.Which of the following methods is the most effective for picking the pivot element ?
First element
Last element
Median-of-three partitioning
Random element
41.Find the pivot element from the given input using median-of-three partitioning method. 8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
8
7
9
6
42.Which is the safest method to choose a pivot element ?
Choosing a random element as pivot
Choosing the first element as pivot
Choosing the last element as pivot
Median-of-three partitioning method
43.What is the average running time of a quick sort algorithm ?
O(N^2 )
O(N)
O(N log N)
O(log N)
44.Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
Merge sort
Shell sort
Insertion sort
Bubble sort
45.Quick sort uses join operation rather than merge operation.
True
False
46.How many sub arrays does the quick sort algorithm divide the entire array into?
One
Two
Three
Four
47.Which is the worst method of choosing a pivot element ?
First element as pivot
Last element as pivot
Median-of-three partitioning
Random element as pivot
48.Which among the following is the best cut-off range to perform insertion sort within a quick sort ?
N=0-5
N=5-20
N=20-30
N>30
49.Recursion is a method in which the solution of a problem depends on ____________
Larger instances of different problems
Larger instances of the same problem
Smaller instances of the same problem
Smaller instances of different problems
50.Which of the following problems can’t be solved using recursion?
Factorial of a number
Nth fibonacci number
Length of a string
Problems without base case
Friday, October 09, 2020
Algorithms Multiple choice questions
Tuesday, June 02, 2020
Time complexities and asymptotic notation
Searching
|
Algorithm |
Data Structure |
Time Complexity |
Space Complexity |
|
|
Average |
Worst |
Worst |
||
|
Graph
of |V| vertices and |E| edges |
- |
O(|E|
+ |V|) |
O(|V|) |
|
|
Graph
of |V| vertices and |E| edges |
- |
O(|E|
+ |V|) |
O(|V|) |
|
|
Sorted
array of n elements |
O(log(n)) |
O(log(n)) |
O(1) |
|
|
Array |
O(n) |
O(n) |
O(1) |
|
|
Shortest path by Dijkstra, |
Graph
with |V| vertices and |E| edges |
O((|V|
+ |E|) log |V|) |
O((|V|
+ |E|) log |V|) |
O(|V|) |
|
Shortest path by Dijkstra, |
Graph
with |V| vertices and |E| edges |
O(|V|^2) |
O(|V|^2) |
O(|V|) |
|
Graph
with |V| vertices and |E| edges |
O(|V||E|) |
O(|V||E|) |
O(|V|) |
|
Sorting
|
Algorithm |
Data Structure |
Time Complexity |
Worst Case Auxiliary Space Complexity |
||
|
Best |
Average |
Worst |
Worst |
||
|
Array |
O(n
log(n)) |
O(n
log(n)) |
O(n^2) |
O(n) |
|
|
Array |
O(n
log(n)) |
O(n
log(n)) |
O(n
log(n)) |
O(n) |
|
|
Array |
O(n
log(n)) |
O(n
log(n)) |
O(n
log(n)) |
O(1) |
|
|
Array |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
|
|
Array |
O(n) |
O(n^2) |
O(n^2) |
O(1) |
|
|
Array |
O(n^2) |
O(n^2) |
O(n^2) |
O(1) |
|
|
Array |
O(n+k) |
O(n+k) |
O(n^2) |
O(nk) |
|
|
Array |
O(nk) |
O(nk) |
O(nk) |
O(n+k) |
|
Heaps
|
Heaps |
Heapify |
Find Max |
Extract Max |
Increase Key |
Insert |
Delete |
Merge |
|
- |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(m+n) |
|
|
- |
O(n) |
O(n) |
O(1) |
O(1) |
O(1) |
O(1) |
|
|
O(n) |
O(1) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(m+n) |
|
|
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
|
|
- |
O(1) |
O(log(n))* |
O(1)* |
O(1) |
O(log(n))* |
O(1) |
Graphs
|
Node
/ Edge Management |
Storage |
Add
Vertex |
Add
Edge |
Remove
Vertex |
Remove
Edge |
Query |
|
O(|V|+|E|) |
O(1) |
O(1) |
O(|V|
+ |E|) |
O(|E|) |
O(|V|) |
|
|
O(|V|+|E|) |
O(1) |
O(1) |
O(|E|) |
O(|E|) |
O(|E|) |
|
|
O(|V|^2) |
O(|V|^2) |
O(1) |
O(|V|^2) |
O(1) |
O(1) |
|
|
O(|V|
⋅ |E|) |
O(|V|
⋅ |E|) |
O(|V|
⋅ |E|) |
O(|V|
⋅ |E|) |
O(|V|
⋅ |E|) |
O(|E|) |
Data Structures
|
Data Structure |
Time Complexity |
Space Complexity |
|||||||
|
Average |
Worst |
Worst |
|||||||
|
Indexing |
Search |
Insertion |
Deletion |
Indexing |
Search |
Insertion |
Deletion |
||
|
O(1) |
O(n) |
- |
- |
O(1) |
O(n) |
- |
- |
O(n) |
|
|
O(1) |
O(n) |
O(n) |
O(n) |
O(1) |
O(n) |
O(n) |
O(n) |
O(n) |
|
|
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
|
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
O(n) |
O(1) |
O(1) |
O(n) |
|
|
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n
log(n)) |
|
|
- |
O(1) |
O(1) |
O(1) |
- |
O(n) |
O(n) |
O(n) |
O(n) |
|
|
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
|
|
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
O(n) |
O(n) |
O(n) |
O(n) |
|
|
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
|
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
|
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
- |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
|
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(log(n)) |
O(n) |
|
Notation for asymptotic growth
|
letter |
bound |
growth |
|
(theta)
Θ |
upper
and lower, tight[1] |
equal[2] |
|
(big-oh)
O |
upper,
tightness unknown |
less
than or equal[3] |
|
(small-oh)
o |
upper,
not tight |
less
than |
|
(big
omega) Ω |
lower,
tightness unknown |
greater
than or equal |
|
(small
omega) ω |
lower,
not tight |
greater
than |