How to solve T(n)=4T(sqrt(n/2))+n^(3/2)

by

The time function is:

enter image description here

We can make this substitution:

enter image description here

And thus:

enter image description here

Now the i + 1th expansion of the time function gives a term:

enter image description here

And the termination index of i, assuming T(0) = 0:

enter image description here

And so the time complexity is given by:

enter image description here

Unfortunately, this is non-analytical (no elementary function representation).

Instead, however, we can make an extremely crude approximation which will almost certainly flabbergast every math-mo out there. Taking the terms at either end of the sum:

enter image description here

Assuming m is large, the first term is much much larger than the last. So we can make a lower bound on the series:

enter image description here

EDIT: Apologies, the sum starts from i = 0, including the last 2^(1.5*m) term. BUT the time complexity bound is still the same. Also I should have used big-Omega notation not big-O…

More Related Contents:

  1. Computational complexity of Fibonacci Sequence
  2. Finding Big O of the Harmonic Series
  3. What is a plain English explanation of “Big O” notation?
  4. How can I find the time complexity of an algorithm?
  5. Time complexity of nested for-loop
  6. What is O(log(n!)) and O(n!) and Stirling Approximation
  7. What would cause an algorithm to have O(log log n) complexity?
  8. What is O(log(n!)), O(n!), and Stirling’s approximation?
  9. Is there anything that guarantees constant time for accessing a property of an object in JavaScript?
  10. Sorting in linear time? [closed]
  11. What is the complexity of this simple piece of code?
  12. Why do we ignore co-efficients in Big O notation?
  13. Can an O(n) algorithm ever exceed O(n^2) in terms of computation time?
  14. What is the time complexity of Python list’s count() function?
  15. What is the time complexity of the sleep sort?
  16. Do iterative and recursive versions of an algorithm have the same time complexity?
  17. Computational complexity of base conversion
  18. What is the computational complexity of `itertools.combinations` in python?
  19. O(3^n) exponential time complexity [closed]
  20. Showing the order of growth of the function
  21. Big O, how do you calculate/approximate it?
  22. How do I profile a Python script?
  23. A Regex that will never be matched by anything
  24. Argument for O(1) average-case complexity of heap insertion
  25. What is time complexity of a list to set conversion?
  26. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  27. Finding the most frequent character in a string
  28. Hashtable in C++?
  29. What’s the time complexity of iterating through a std::set/std::map?
  30. What is the cost/ complexity of insert in list at some location?

Leave a Comment