Register

Consider an algorithm A which solves problems by dividing them into seven sub-problems

6,667 views
1 1 vote

Consider an algorithm A which solves problems by dividing them into seven sub-problems each with half the size of the original problem, recursively solving each subproblem, and then combining the solutions in linear time. What is the time complexity of this algorithm?

  1.   Almost equal to O(n2)
  2.   Almost equal to O(n3)
  3.   O(2n)
  4.   None of these

1 Answer

Best answer
3 3 votes
I think , Recurrence relation for the above will be :

T(n) =  7 * T(n/2) +  n

After solving :  

Complexity : (n^log2(7) )     base = 2

almost : O( N^2.8)  something   we can say O(N^3)
• selected by
Voting & Accepting an answer helps improve the community
← Previous · C ProgrammingNext → · Made Easy
← Previous in category · minimum difference b...Next in category → · Suppose we have a he...
Position:
Show:

Related questions

0 0 votes
1 answers 1 answer
1.1k
1.1k views
dhruba asked May 29, 2023
1,077 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...
0 0 votes
1 1 answer
1.4k
1.4k views
sonalrawat asked Aug 21, 2023
1,411 views
We are given a directed graph, represented as an adjacency list, in which each vertex has at least one incoming edge and one outgoing edge. We would like to print out for each vertex j the list of vertices pointing into j. What is the most accurate description of the complexity of computing these quantities in terms of n, the number of vertices, and m, the number of edges? O(n2) O(nm) O(m) O(n)
0 0 votes
2 2 answers
1.2k
1.2k views
radha gogia asked Jul 17, 2015
1,239 views
what is the use of reducing a problem for which no polynomial time algorithm exist into some another problem ?
If I have a problem A for which no polynomial time algo exists then what do we achieve by reducing it to another problemB and then proving by contradiction that if we cou...
9 9 votes
2 answers 2 answers
23.5k
23.5k views
radha gogia asked Jul 19, 2015
23,472 views
Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
(A) Insertion Sort with time complexity O(kn)(B) Heap Sort with time complexity O(nLogk)(C) Quick Sort with time complexity O(kLogk)(D) Merge Sort with time complexity O(...