Algorithm Basic Level Test

Find the time complexity of following recurrence relation?
T(n) = 5T(n-47) + O(1) and
T(0)=1

Arrange the following functions according to growth of increasing.

Consider the following code :

Search(int n){
if(n<2)
then return;
else{
s=0;
for(i=1;i<=8;i++){
Search(n/2);
}
for(i=1;i<n*n;i++){
for(j=1;j<n;j=j*2){
s=s+i;
}
}
}
}

Assume s is a global variable.Find the complexity of the given Search(n)?

What will be the time complexity for the following recurrence relation?
T(n)=8T(n^1/2)+(log n)² if n>2
= 1,Otherwise

Which of the following sorting techniques have best time complexity, if complexity is measured in terms of number of comparison?

The number of distinct minimum spanning trees for the weighted graph below is _____

The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A,C),(B,C),(B,E),(E,F),(D,F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is_______________.

A file contains characters a,e,i,o,u,s and t with frequencies 10,15,12,3,4,13 and 1 respectively. If we use Huffman Coding for data compression then the average code length will be –

Four matrices M1, M2, M3, and M4 have dimensions p x q, q x r, r x s, and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 x M2) x (M3 x M4)) total number of scalar multiplications is pqr + rst + prt.

When multiplied as (((M1 x M2) x M3) x M4) the total number of scalar multiplications is pqr + prs + pst.

If p = 10, q = 100, r = 20, s = 5, and t = 80, then what is the minimum number of scalar multiplications needed ?

Consider two strings A=“qpqrr” and B=“pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x+10y= ___.