Solution

The asymptotic notations are following the given order.

Constant < logarithmic < linear < polynomial < exponential < factorial

We can solve these type of problems by using three methods

1. Apply log on both sides
2. Apply larger common mathematical value
3. Through asymptotic order.

The statements following asymptotic order are S2 < S1 < S3 .

Option-A: FALSE: f(n)=O(h(n)) and g(n)=O(h(n)) because h(n) is asymptotically larger.

Option-B: FALSE: f(n)=O(h(n)) and h(n)≠O(g(n)) because g(n) is asymptotically smaller than h(n).

Option-C: FALSE: g(n)=O(h(n)) and f(n)≠O(g(n)) because f(n) is greater than g(n). So we can represent f(n)=O(h(n)) instead of f(n)=O(g(n))

Option-D: TRUE: g(n)=O(h(n)) and h(n)=Ω(f(n)) because g(n) is smaller than h(n) and f(n) is smaller than h(n).

Note: BigOh = Worst case (or) upper bound

BigTheta= Average case

BigOmega= Best case (or) lower bound

Solution

According to given conditions Bob < John < Alice in terms of BigOh notations.

Option-A: FALSE: Bob=O(Alice) and Alice≠O(John) because Alice will take maximum time to reach 100 meters.

Option-B: FALSE: Alice ≠ O(John) and John≠O(Bob)

Option-C: FALSE: John ≠ O(Bob) and Bob=O(Alice)

Option-D: TRUE: John=O(Alice) and Alice≠O(Bob)

Solution

T(n)=T(n/4)+T(n/2)+n^2

Using recursion tree method

We can extract the given condition into

Solution

T(n) = T(n-1) + 1/n --- (I)

T(n-1) = T(n-2) + 1/n-1 ---(II)

T(n-2) = T(n-3) + 1/n-2 ---(III)

Putting (II) in (I),

T(n) = T(n-2) + 1/n-1 + 1/n ---(IV)

Putting (III) in (IV),

T(n) = T(n-3) + 1/n-2 + 1/n-1 + 1/n

⋮

T(n) = T(n-k) + 1/n-(k+1) + … 1/n-2 + 1/n-1 + 1/n

Base condition is,

T(1) = 1

So, n-k = 1

k = n-1

So, T(n) = T(1) + 1/n-(n-1) + ½ + … + 1/n-1 + 1/n

= 1 + 1/1 + ½ + ⅓ + … + 1/n

= O(log n)

Solution

Bob(int n)

{

for(i=n; i>=1; i=i/2) → T(logn)

for(j=1; j<=n; j=j*2) → T(logn)

printf("GATE 2021"); → T(1)

}

We are given independent loops but nested. The ith loop will take logn time and jth loop will take logn time.

= T(logn)*T(logn)

= O(log^2 n)

Solution

Solution

→ In recursion code segments we will consider only the recursion part to find time complexity. We never consider the dependent value of the recursion function.

→ We will consider the recursion part in either “if” or “else” conditions. Both conditions will give the recurrence relationship is Bob(n/2)+Bob(n/2)+1

We will not consider the dependent value of the else statement “3”.

→ We can rewrite the condition into T(n)=T(n/2)+T(n/2)+1

T(n)=2T(n/2)+1

Apply masters theorem,

a=2, b=2, k=0, p=0

Case-1: a>b^k

⇒ 2>2^0

O(n^log₂2 n)

O(n)

Solution

Solution

Method-2:

Let n=1024

Iteration-1: i=1 j=0 k=1024

Iteration-2: i=2 j=0 k=2048

Iteration-3: i=4 j=0 k=3072

Iteration-4: i=8 j=0 k=4096

Iteration-5: i=16 j=0 k=5120

Iteration-6: i=32 j=0 k=6144

Iteration-7: i=64 j=0 k=7168

Iteration-8: i=128 j=0 k=8192

Iteration-9: i=256 j=0 k=9216

Iteration-10: i=512 j=0 k=10240

Iteration-11: i=1024 j=0 k=11264 // Prints the value but stops the execution.

We can clearly understood that i-value executing “logn” time and j value is dependent to the ith value but it is executing only “1” time.

We will not consider “k” value for time complexity because we will consider it as constant.

So, overall time complexity is T(1)*T(log₂n)*T(1)*T(1)*T(1)

= O(log₂n)

Solution

The given code is nothing but the Tower of Hanoi.

Bob(int n, int a, int b, int c)

{

if(n==1)

return 1; → T(1)

else

{

Bob((n-1), a, c, b) → T(n-1)

printf(“GATE 2021’); → T(1)

Bob((n-1), c, b, a) → T(n-1)

}

}

Recurrence relation for given recursion code segment is T(n)=T(n-1)+T(n-1)+1

We can rewrite in to 2T(n-1)+1

Solution

→ The above code segment is a combination of iterative and recursion. Even though it is a combination of iterative and recursion we have to find worst case time complexity.

→ The above code segment given two independent loops so we have to identify which is larger to find worst case time complexity.

Solution

S1: FALSE: 2T(n/2)-4T(n/2)+1 is not solvable by using the master's theorem because masters theorem will allow the recurrences in the form of aT(n/b)+f(n) or aT(n/b)+n^k log^p n.

S2: FALSE: If for an algorithm time complexity is given by O((3⁄2)^n) then complexity will be exponential.

The growth rate of O((3⁄2)^n) or O(1.5)^n function will be exponential therefore complexity will be exponential.

Solution

We can solve this problem by 2 methods:

1. Apply log on both sides
2. Using asymptotic growth functions( constant, logarithmic, linear, polynomial and exponential)

In this problem, 2nd method is most suitable

Constant < logarithmic < linear < polynomial < exponential

Step-1:

Solution

This type of problem, we have to consider worst case time complexity, it means that all possibilities.

According to the flow chart, there are a total 7 worst case possibilities of function calls.

Flowchart for recursive function A(n):

The remaining function calls/return statements will execute only a constant amount of time.

So, the total function calls 7.

The Recurrence will be

A(n) = 7A(n/3) + O(1)

Apply Master’s theorem,

A=7, b=3, k=0, p=0

Solution