search
Log In

Recent questions tagged divide-and-conquer

0 votes
3 answers
3
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort. O($n^2$) O($n^3$) O(nlogn) O(n)
asked Sep 2, 2019 in Algorithms ajaysoni1924 1.2k views
0 votes
0 answers
4
Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of $A[1 j]$, extend the ... a maximum subarray of the form $A[i...j+1]$ inconstant time based on knowing a maximum subarray ending at index $j .$
asked Apr 5, 2019 in Algorithms akash.dinkar12 101 views
0 votes
0 answers
5
Suppose we change the definition of the $maximum-subarray problem$ to allow the result to be an empty subarray, where the sum of the values of an empty subarray is $0$. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?
asked Apr 5, 2019 in Algorithms akash.dinkar12 57 views
0 votes
0 answers
6
Implement both the brute-force and recursive algorithms for the $maximumsubarray$ problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?
asked Apr 5, 2019 in Algorithms akash.dinkar12 68 views
0 votes
0 answers
7
Write pseudo code for the brute-force method of solving the $maximum-subarray$ problem. Your procedure should run in $\Theta(n^2)$ time.
asked Apr 5, 2019 in Algorithms akash.dinkar12 79 views
0 votes
0 answers
8
how many terms will be computed to determine the value of C(10,8) using divide and conquer algo ? 88 89 90 91
asked Dec 24, 2018 in Algorithms Satbir 127 views
0 votes
3 answers
9
0 votes
1 answer
10
Is the answer to this solution is O( n2 log (n) ) or O( n log (n) )
asked Sep 3, 2018 in Algorithms manvi_agarwal 384 views
1 vote
2 answers
11
https://gateoverflow.in/?qa=blob&qa_blobid=11583750777176064728 Approach please
asked Sep 3, 2018 in Algorithms manvi_agarwal 172 views
1 vote
0 answers
12
A student develops a technique to multiply two 2×2 matrices. The technique requires six multiplications. The complexity of the module that combines the module is O(n2). Then the recursive equation depicting the complexity of the algorithm is (A) T(n) = 6T(n/3) + O(n2) (B) T(n) = 6T(n/2) + O(n2) (C) T(n) = 6T(2n ) + O(n2) (D) T(n) = T(n/2) + 6 O(n2)
asked Aug 16, 2018 in Algorithms rohan.1737 127 views
2 votes
1 answer
13
Leading element in an array of n elements is the element which occurs more than n/2 times in the array. a) What is the time complexity to find whether a leading element exists or not in a sorted array of n elements? b)What is the time complexity to find whether a ... are between 0 to n? c)What is the time complexity to find whether leading element exists or not in an unsorted array of n elements?
asked Aug 7, 2018 in Algorithms Sambhrant Maurya 462 views
3 votes
0 answers
14
Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10}, the maximum subarray sum is 45. The naive solution for this problem is to calculate sum of all subarrays starting with every element and return the ... time complexity using Divide and Conquer. A O(n) B O(nLogn) C O(Logn) D O(n2) Correct answer is B. O(nLogn) How?
asked Jul 27, 2018 in Algorithms Rishav Kumar Singh 663 views
0 votes
1 answer
15
Given two sorted double linked list L1 and L2 of n elements each, which of the following are true? (A) L1 and L2 can be merged into single sorted list in Θ(n) time. (B) L1 and L2 can be merged into single sorted list in Θ(1) time. (C) L1 and L2 can be merged into single sorted list in Θ(nlogn) time. (D) L1 and L2 can be merged into single sorted list in Θ(n2) time.
asked Jul 5, 2018 in Algorithms JAYKISHAN 234 views
2 votes
0 answers
16
You have an array A with n JPEG images some of which are identical. You can check if two objects are equal but you cannot compare them in any other way-i.e. you can check A[i] == A[j] and A[i] != A[j], but comparisons such as A[i] < A[j] are not ... half of its elements are equal to each other. Use divide and conquer to come up with an O(n logn ) algorithm to determine if A has a majority element.
asked May 2, 2018 in Algorithms Kushagra Chatterjee 237 views
0 votes
1 answer
17
find T(n) = T(n-1)*T(n-2), given T(1) = a and T(2) = b
asked Apr 25, 2018 in Algorithms bittu 429 views
0 votes
0 answers
18
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?
asked Jan 12, 2018 in Algorithms iarnav 179 views
1 vote
1 answer
19
Consider a set of 156 elements to find minimum and maximum elements in the given set, the minimum number of comparisons required is___? You have given an array of 512 elements,minimum number of comparisons required to find out second largest element among all will be___? 230 & 517 229 & 516 231 & 518 232 & 519
asked Jan 5, 2018 in Algorithms vinay9427 199 views
1 vote
1 answer
20
2 votes
2 answers
22
Do we need to study the Strassens's algorithm in detail like proof or working of that algorithm or we just need to know the time complexity of the algorithm because I can't find it's explanation anywhere?
asked Oct 9, 2017 in Algorithms Manasi Srivastava 363 views
1 vote
0 answers
23
I implemented maximum sub-array problem with Divide and Conquer approach in c++ and python. I got little bit of confusion in the implementation.Below are the implementations. I got different results when I change the for loop of both c++ and python code.in first I implemented something ... loop)) In first case I am getting right output i.e 43 but in 2nd I am getting 56 as the output! Please help!
asked Jul 21, 2017 in Algorithms Alabhya Pandey 169 views
2 votes
3 answers
24
how to apply master's method for this recurrence relation $T\left ( n \right )= {}\sqrt{n}T\left ( {\sqrt{n}} \right )+n$
asked May 19, 2017 in Algorithms Devasish Ghosh 364 views
3 votes
1 answer
26
CAN SOMEONE SOLVE THE NUMBER OF COMPARISIONS FOR COMPUTING MIN AND MAX IN AN ARRAY USING DIVIDE N CONQUER?? RECURRENCE RELATION IS $ T(n) = 2 T(\frac{n}{2}) + 2 $ IT SHOULD COME TO $ \frac{3*n}{2} - 2 $ ??
asked Mar 23, 2017 in Algorithms sushmita 942 views
2 votes
1 answer
27
Reply with solution @Arjun sir,@habibkhan,@vijaycs
asked Feb 7, 2017 in Algorithms Shubham Sharma 2 431 views
3 votes
2 answers
28
Consider an array containing ‘n’ elements. The elements present in an array are in arithmetic progression, but one element is missing in that order. What is the time complexity to find the position of the missing element using divide and conquer?
asked Nov 25, 2016 in Algorithms Shubham Pandey 2 1.7k views
...