What is the time complexity of basic recursion that decrements by 1?
If it decrements by 1 (e.g., n-1) and makes a single call, it forms a straight line of N calls, resulting in O(N) Linear Time.
Verify This Answer
Cross-check this information using these trusted sources:
More FAQs in Analyzing the Time Complexity of Recursive Functions
You determine the total number of times the function is recursively called (the nodes in the recursion tree) and multiply it by the amount of non-recursive work done in each call.
Because instead of decrementing by 1, it divides the input size by 2 on each recursive call, slashing the required number of calls logarithmically.
Traversing an entire tree to visit every node is O(N) because you must process all N nodes. Searching a perfectly balanced Binary Search Tree is O(log N).
Still have questions?
Browse all our FAQs or reach out to our support team