Register

Divide and Conquer

446 views
0 0 votes
Let us say we are given 2 binary strings of n-bits each which represent the values
of two integers. We wish to calculate the product of these 2 integers. Using Divide
and Conquer approach we can reduce the number of intermediate products in the
each step by 1. In general, if the number of splits in each step is k, then what is the
time complexity for calculating the product of the 2 integers?

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · SELF DOUBTNext → · Natural Join
← Previous in category · PRE-ORDER, POST-ORDE...Next in category → · Gateforum Test Serie...
Position:
Show:

Related questions

5 5 votes
1 1 answer
210
210 views
GO Classes asked Aug 5
210 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
210
210 views
GO Classes asked Aug 4
210 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 1 answer
377
377 views
GO Classes asked Aug 26, 2025
377 views
GO Classes DPP | Algorithms | Divide and conquer
LazySort(A): n = length(A) if n = 0 or n = 1: return A pivot = A # always pick the first element left = LazySort(elements < pivo...
1 1 vote
1 answers 1 answer
1.1k
1.1k views
Emankashyap asked Apr 30, 2024
1,057 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(...