GO2019-FLT1-48

419 views

Consider the following piece of pseudo-code:

A(n){
if(n==0) return 1;
return A(√n) + B(n) + C(n) + D(n);
}
B(n){
if (n==0) return n;
return B(n-1);
}
C(n){
return A (√n);
}
D(n){
return n;
}

What is the time complexity in terms of Big $\Theta$ notation for the function call to procedure A?

1. $\Theta(n)$
2. $\Theta(n \log n)$
3. $\Theta(n \log \log n)$
4. $\Theta(n^2 \log n)$

retagged
1
Function (B) has time complexity of O(n)

Function (D) has O(1)

Now, I Re-write the return statement of A as

return $A(\sqrt n)+O(n)+A(\sqrt n)+O(1)$

So, I form my recurrence for A as

$T(n)=2T(\sqrt n)+O(n)$

How Do I solve it?
1
Read cormen book for this. Dont apply masters theorem all the time. it wont work here. In cormen book they have substituted it properly and solved.
0
Means, even my recurrence for A is incorrect?
0
Recurrence is fine. Just solve it by proper substitution. You will have your answer!!!
0

By solving your recurrence relation I got O ( n log n )

but it's not the correct answer :/

1

@Ruturaj Mohanty I changed the options and also the notation to Big-Theta - otherwise there can be multiple answers.

Time complexity for $B(n), T_B(n) = T_B(n-1) + 1 \implies T_B(n) = \Theta(n)$

Time complexity for $D(n) = \Theta(1)$

So, time complexity for $A(n), T_A(n) = 2T_A\left(\sqrt n\right) + \Theta(n)$

For sake of simplicity rewriting $T_A$ as $S,$ we get

$S(n) = 2S(\sqrt n)+ \Theta(n)$

Substituting $n = 2^m$

$S(2^m) = 2S(2^{m/2}) + \Theta (2^m)$

Now taking $S(2^m) = R(m)$

$R(m) = 2R(m/2)+ \Theta(2^m)$

On this we can apply Master's theorem case 3, and we get $R(m) = \Theta (2^m)$

$\implies S(2^m) = \Theta(2^m)$

$\implies S(n) = \Theta(n)$

selected
1
shouldn't it be $R(m)=2R(m/2)+\Theta(2^m)$ ?
0
Thanks. Corrected 👍
0

@Arjun

Sir could please give me reference for Masters theorem case 3 as u write in answer??

4
That is in Cormen rt? Anyway when the functional part is exponential in the recurrence it should dominate the recursive part and Case 3 becomes trivial.
0

@Arjun sir,

you took S(2^m)=R(m) then s(2^(m/2)) should be R(m^1/2) but not R(m/2)

Logic: 2^m = x

m = log x

m/2 = (log x)/2

2^(m/2) = 2 ^ (log (x^1/2)) = x^1/2

Kindly correct me if i am wrong.

2
See I did not substitute $2^m = x.$ Actually I used a different function $S(x)$ and $R(x) = S(2^x)$ or $S(x) = R(\log_2 x)$
1
Got it. Thanks sir🙂.

Related questions

1
163 views
Consider the two given functions: int fun1(int x, int y) { if (y==0) return 0; return (x+fun2(x, y-1)); } int fun2(int x, int y) { if (x==0) return y; return fun2(x-1, x+y); } What will be the value returned by $\text{fun1}(4, 4)$ ____
Consider the following piece of code: int function(int a[], int n, int x) { int i; for (i=0; i<n && a[i]!=x;i++); if (i==n) return -1; else return i; } A function call is made with the arguments as follows: $a[]=\{5, 32, 1, 9, 7, 2\}$ $n=6$ $x=8$ What is the values returned by the above code?
A sequential search operation is performed on an array $A$ for the key value of $'x'$ (ignore quotes). Consider the following piece of assembly language code that uses back patching to perform the sequential search. i=0; P: if (i<A.length) goto ____; Q: goto ____; R: if (x==A[i] ... What should be the correct values in the blanks provided ordered from top to bottom? R T U P R U T P P U T R P T U R
Consider the following modified Heapify and Build_heap procedure. void Heapify(int* A, int i, int n) { int left=2*i+1; int right=2*i+2; int mid=i; if (left<=n && right <=n) { if ((A[left] > A[right] && A[left]< A[i]) || A[left]<A[right] && A[left] >A[i]) mid=left; else if((A[left<A[right] && A[right]<A[i]) ... $6 \: 8 \: 1 \: 9 \: 4$ $9 \: 6 \: 1 \: 8 \: 4$ $6 \: 9 \: 1 \: 8 \: 4$