The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

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

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

4)T(n)=T(n/2)+T(n/4)+T(n/8)+n.

Use Masters theorem

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

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

4)T(n)=T(n/2)+T(n/4)+T(n/8)+n.

Use Masters theorem

+1 vote

Question 1: Master Theorem not possible since b=1, which is not greater than 1.

Question 2: Master Theorem not possible since b=1, which is not greater than 1.

Question 3:

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

Now, Master Theorem not possible since b=1, which is not greater than 1.

Question 4: T(n)=T(n/2)+T(n/4)+T(n/8)+n

Roughly, T(n) can be written as T(n)<T(n/2)+T(n/2)+T(n/2)+n, which can be further reduced to

T(n)<3T(n/2) + n

Now, a = 3, b=2, k=1, p=0

Clearly, a > b^{k} i.e. 3>2^{1}.

So, Case 1 satisfies. Therefore, T(n)=Theta(n^{lg3}) = Theta(n^{1.584962...}) = Theta(n)

I hope it helps. :)

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.3k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 795
- Others 1.2k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,138 questions

36,959 answers

92,024 comments

34,803 users