How to calculate the upper bound time complexity (`"big O`") of a recursive function?
Suppose I have a recursive function T, and I want to calculate the upper bound timer complexity of this function.
T(1) = 3
T(n) = 3T(n/3) + 3.
How can I find the upper bound of the time complexity of T(n)?
Solution
Use the master theorem case 
where a=3, b=3, c=0.
I highly recommend the MIT lectures on Algorithms. You can learn more about the Master theorem in lecture 2
- Determining if two rays intersect
- How to generate a random array from the values of another array, the sum of whose values are within a pre-determined range?
- Efficient Algorithm for Minimum Euclidean Distance Between Points in Non-Overlapping Regions in a 2D Array
- Are there known implementations of the CIEDE2000 or CIE94 Delta-E color difference calculation algorithm?
- Why can’t you use Hash Tables/Dictionaries in Counting Sort algorithm?
- Why does Algorithms Illuminated use Turing reductions instead of Karp for NP-hardness
- Fast algorithm for repeated calculation of percentile?
- Is there anyway to speed this up?
- Understanding Time complexity calculation for Dijkstra Algorithm
- Mathematical explanation of Leetcode question: Container With Most Water
- SICP example: Counting change, cannot understand
- Leader clustering algorithm explanation
- Quicksort with Python
- Most performant approach to find closest match from unordered collection
- How to get specified number of decimal places of any fraction?
- Efficient calculation of Fibonacci series
- How to compute the integer absolute value
- Fenwick tree vs Segment tree
- How to create an auxiliary data structure to keep track of heap indices in a minheap for the decrease_key operation in c++
- Algorithm to select multiple non-overlapping subsequences of given sequence
- Processing of mongolian names
- How to divide by 1000000 without resulting in: undefined reference to '__udivdi3'
- C++ rand() each number only once
- What is the cleanest way to create a timeout for a while loop?
- Fast sigmoid algorithm
- What is the most efficient algorithm for merging sorted lists with a carry-forward mechanism for missing keys?
- count number of valid substrings
- How to sort depended objects by dependency
- Dutch national flag on a Turing Machine
- Fast way to expand split list into index list