Register

divide and conquer

1,000 views
0 0 votes

in questions like how many multiplications of n are needed are being solved by dividing n into n/2 * n/2 and then end up with recurrence t(n) = t(n/2) + O(1)

 

How to reach this type of analysis where we get to know that we have to divide n into halves?

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · cfl or notNext → · Articulation point i...
← Previous in category · recurrece relation ...Next in category → · recurrence eq
Position:
Show:

Related questions

5 5 votes
1 1 answer
204
204 views
GO Classes asked Aug 5
204 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide and Conquer
Suppose $n$ elements are divided into groups of $r$ elements. The median of each group is found, and the median of these group medians is used as the selection pivot.For ...
4 4 votes
1 1 answer
204
204 views
GO Classes asked Aug 4
204 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide and Conquer
There are $n$ cities, and exactly $k$ of them are contaminated. A test on any subset tells whether at least one contaminated city is present in that subset.A divide-and-c...
1 1 vote
1 answers 1 answer
1.1k
1.1k views
Emankashyap asked Apr 30, 2024
1,055 views
Divide and conquer
In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is.....a)O(nlogn)b)O(...
0 0 votes
1 answers 1 answer
1.1k
1.1k views
dhruba asked May 29, 2023
1,075 views
Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given by f(n) = Θ(n^c). The Master Theorem classifies this into different cases based on the value of c in relation to log_b(a). Could you explain the intuition and reasoning behind these classifications?
Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given b...