recursiontime-complexityasymptotic-complexity
Time complexity of the following recursive function
What is the time complexity of the following recursive function
int DoSomething(int n){
if(n<=2)
return 1;
else
return (DoSomething(floor(sqrt( n) )) + n);
}
Options are:-
- O(n^2)
- O(n log n) //all logs are with base 2
- O(log n )
- O(log log n )
Solution
The time complexity function is (ignoring floor as it is asymptotically irrelevant):
We need to find m when the algorithm terminates, i.e. when:
- 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
- How do python list items change if they are involved in recursive loops?
- Windows batch file to recursively use Imagemagick command to process .jpg images in a folder and subfolders?
- Validate that a multidimensional array is wholly found in another, potentially larger multidimensional array
- Recursively traverse a multidimensional array and print hierarchical sets of checkboxes
- TypeScript type definition for an object property path
- How to understand foldTree function?
- sorting stack in ascending order using recursion (colsed)
- Check if a string is palindrome in C
- Find a Path to Root in Tree-structured Data (Recursive Function in Python3)
- Avoid RecursionError in turtle paint code
- Can't change recursion limit python
- Creating a recursive method for Palindrome
- Recursion, Parameter & Return Types
- Optimization of tail recursion in R
- Clarification on Recursion in mergeTwoLists for Linked Lists
- Recursively merge two arrays and keep keys
- Checking an integer is palindrome using recursion without using any extra reverse function