199 views
1 votes
1 votes
Generally a recurrence relation is given as

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

where a is no of sub prblm of size n/b each.

Can there be any real scenario where a>b.

I mean if n is divided into n/b problems then there must be at most b problems...So that b*n/b=n.....then how can a>b??

Please log in or register to answer this question.

Related questions

836
views
1 answers
0 votes
Mak Indus asked Nov 5, 2018
836 views
The recurrence equation:T(1) = 1T(n) = 2T(n - 1) + n, n ≥ 2evaluates to(a) 2n + 1 - n - 2 (b) 2n - ... (d) 2n - nSolution: Option (a)
3.3k
views
1 answers
4 votes
Lakshman Bhaiya asked Jan 15, 2018
3,317 views
Which of the following represents most appropriate asymptotic solution for given reccurance:(A) O(n)(B) O(log n)(C) O(log log n)(D) O(log n)2
1.1k
views
1 answers
0 votes
Saurav asked Aug 31, 2015
1,113 views
The number of leaf nodes in the recurrence tree of the recurenceT(n) = T(n/4) + T(n/2) + n^2
228
views
1 answers
1 votes
jenilS7 asked Mar 18
228 views
What is the returned value by the given function below.Algo fun(n){ If(x<=2) return 1; Else { Return fun(n1/2) + ... }}Note : Assume that all the syntax and data type constraints are valid and just check algorithm.