search
Log In
0 votes
68 views
T(n) = 3T( n/3 ) + n/2

The answer to the above question says that case 2 of masters theorem is applied here. How is it so?
in Algorithms 68 views

2 Answers

3 votes

T(n) = aT(n/b) +cnk

here,  T(n) = 3T( n/3 ) + n/2

k=1 ; c =1/2 ;  a=3 ; b=3

a = bk

3  = 31

Complexity = nklogn

= O(nlogn)

1 vote

Case 2: f(n) = nclogkn   c=  $\log_b a$

c=1

 $\log_b a$ =1

Related questions

0 votes
1 answer
1
201 views
I want to learn to find time complexity of the recurrence relation of an algorithm. Please suggest some good links or any gatetoverflow imp questions links to look as examples . Thanks
asked Oct 31, 2018 in Algorithms Mayankprakash 201 views
0 votes
0 answers
2
58 views
When we have to use multiplication and addition while finding the time complexity of an algorithm Eg( n * logn )or (n + logn) Please explain me this concept Thanks
asked Oct 31, 2018 in Algorithms Mayankprakash 58 views
1 vote
1 answer
3
261 views
Consider the following two functions. What are time complexities of the functions? int fun1(int n) { if (n <= 1) return n; return 2*fun1(n-1); } int fun2(int n) { if (n <= 1) return n; return fun2(n-1) + fun2(n-1); } (A) O(2^n) for both fun1() and fun2() (B) O(n) for fun1() and O(2^n) for fun2() (C) O(2^n) for fun1() and O(n) for fun2() (D) O(n) for both fun1() and fun2()
asked Jul 25, 2018 in Algorithms Rishav Kumar Singh 261 views
1 vote
1 answer
4
235 views
In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?
asked Jul 25, 2018 in Algorithms Rishav Kumar Singh 235 views
...