Recurrence Relation Master Theorem
T(n) = 6T(n/3) + n * (n-1)
T(1) = 4
If we have a recurrence relation like above, what should we do?
--> a*T(n/b) + f(n)
--> a*T(n/b) + O(n^d)
--> 6*T(n/3) + O((n^2) - n)
--> 6*T(n/3) + O(n^2)
It seems to like we should use O(n^d). If we go through that way, result is O(n^2).
But I cannot be sure of that. It's like something is missing. Can anyone help to tell is this way true, how to solve this step by step? Thanks in advance.
Solution
In my opinion you can continue to apply the theorem to the next step :
with
According to the 1rst generic form of the master theorem : wikipedia
- Writing code without recursive functions to traverse graphs
- How to recursively merge two multidimensional arrays
- Can a class contain an instance of itself as a data container?
- detecting infinite array recursion in PHP?
- Implement a Knight's Tour algorithm using backtracking in Python
- Managing memory with recursion and for loops (C++20)
- How do python list items change if they are involved in recursive loops?
- Test if a value exist in a multidimensional array whether as a key or a value
- print matrix in spiral order recursively
- Issue with recursive method to extract substring between outer parentheses
- How to reformat a nested array?
- Check if a target sum is possible given a vector of values
- Node.js recursively list full path of files
- Generate all possible combinations of the values in an array JS
- Convert an array of objects into a multidimensional array with parent-child relationships
- What constitutes codata in the context of programming?
- Handling starred and non-starred nodes in a tree transformation
- Using struct member as recursion seed doesn't terminate when self-referencing >1 of itself
- Compute recursively the largest substring which starts and ends with sub and return its length
- Parse a flat, associative array with keys representing a delimited key path into a multidimensional, associative array
- Recursively keep only even values in a multidimensional array
- Creating a waiting function using process.nextTick or setImmediate - node.js
- Why does recursive binding of arrow function in Haskell loop infinitely?
- Deriving a mathematical formulation for my recursive solution?
- Recursive key sorting function is not affecting lower level items
- Merging yaml config files recursively with bash
- Integer Partition (algorithm and recursion)
- How to validate that 2 folders on the same level cannot have the same name in a recursive Angular form array
- Observable recursion (or binding) in Arrows
- Windows batch file to recursively use Imagemagick command to process .jpg images in a folder and subfolders?