Problem solving through programming in C
Rupesh Kumar
Friday March 21 2025
6-8 PM
1. What is the worst case complexity of insertion sort?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Answer: Option d
For the element at the last index: We did (9-1) = 8 comparisons
For the element at index 7 : We did 9-2 = 7 comparisons
.
.
.
For the element at index 1 we did 9-8 = 1 comparison
8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 8 * 9 /2 = 36
Let’s generalize this for an array with x elements: 1 + 2 + 3 + … + (x-2) + (x-1)
No of comparisons would be : (x-1) x /2 =
We need to find g(x), such that f(x) <= cg(x)
2. Binary Search is useful when an array is?
a) Sorted
b) Unsorted
c) sorted in ascending order
d) sorted in descending order
Answer: Options a, c, and d
3. Given an array arr = {21, 33, 56, 59, 64, 91, 91, 100,105} and key = 56; what
are the mid values (corresponding array elements) generated in the first and
second iterations in a binary search?
a) 85 and 12
b) 85 and 34
c) 64 and 33
d) 62 and 47
{21, 33, 56, 59, 64, 91, 91, 100,105}
Answer: Option C
4. Consider the array A[ ]= {100, 11, 24, 5, 1} apply the insertion sort to sort the
array. Consider the cost associated with each insertion step (comparisons +
swapping) is 25 rupees, what is the total cost of the insertion sort for sorting
the entire array?
a) 25
b) 50
c) 75
d) 100
Answer: We need 4 insertion steps, each step requires 25 cost, so total 25
x 4 = 100 is the answer. Option d
5. What will be the output?
#include<stdio.h>
#define func1(a,b) a > b ? b : a
#define func2(a,b) {temp=a;a=b;b=temp;}
int main()
{
int a=3, b=5,temp;
if( (3+func1(a,b) ) > b)
func2(a,b);
printf("%d %d", a,b);
return 0;
}
a) 3 5
b) 3 0
c) 5 0
d) 5 3
Answer: Option d
How the program will be inferred by the compiler?
int main()
{
int a = 3, b =5;
if((3+ (a>b?b:a)) > b)
{
temp = a;
a = b;
b= temp;
}
printf(“%d %d”, a,b);
6. Consider an array of elements arr[5]= {5,4,3,2,1}, what are the steps of
insertions done while doing insertion sort in the array.
a) 45321
34521
23451
12345
b) 54312
54123
51234
12345
c) 43215
32154
21543
15432
d) 45321
23451
34521
12345
Answer: Option a
7. We know that insertion sort takes O(𝑛2 ) time (we saw this in question 1).
Device a method by which the complexity can be reduced.
How to find the target index location for value present at index k? We were
doing linear search for finding the element just greater than the element at
index k.
Using binary search with Insertion sort, we cannot decrease the worst case
complexity, but on an average, the algorithm will be more efficient (shifting
values will still need O(n) operations).
Practice Problems:
Write a program in C to find the square of any number using the function.
Write a program in C to check if a given number is even or odd using the
function.
Write a program in C to get the largest element of an array using
functions.