Member Avatar for RehabReda

hi guys
i can't solve this problem
is there any hint???
T(n) = T(n/2 + √n) + √6046
your help will be appreciated

  • 4 Contributors
  • 3 Replies
  • 136 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by anollipian

Dani AI

Generated

Short answer: T(n) = Theta(log n).

The term sqrt(6046) is a constant (about 77.8), so the recurrence T(n) = T(n/2 + sqrt(n)) + sqrt(6046) behaves like a single recursive call that halves the problem size up to a lower-order perturbation. That matches 's intuition and the suggestion from to use substitution; is also correct that standard divide-and-conquer theorems formalize the result.

Sketch of proof (upper bound). For n >= 100 we have sqrt(n) <= n/10, so
n/2 + sqrt(n) <= 0.6 n. Let c = sqrt(6046). Then for n >= 100,
T(n) <= T(0.6 n) + c. Iterating k times gives T(n) <= T(0.6^k n) + c k.
Choose k = ceil(log_{1/0.6}(n/100)) so 0.6^k n <= 100. Thus
T(n) <= T(100) + c·k = O(log n).

Sketch of proof (lower bound). Since sqrt(n) >= 0, n/2 + sqrt(n) >= n/2, so
T(n) >= T(n/2) + c. Iterating k = floor(log_2 n) times gives
T(n) >= T(1) + c·floor(log_2 n) = Omega(log n).

Combining the two bounds yields T(n) = Theta(log n). For completeness: if the additive cost were sqrt(n) (not a constant), summing the per-level costs would give Theta(sqrt(n)) instead.

Recommended Answers

All 3 Replies

Member Avatar for BestJewSinceJC

I would make a guess and then try the substitution method. I'm not very good with recurrences though so use this advice at your own risk (of failure). But the guess I'd make first would take into consideration that for large n, n/2 + root n is controlled by n/2. That square root at the end of the recurrence doesn't matter, I don't think, because it's a constant. After you make the guess though, you substitute and see if it works, so even if your logic sucks, as mine might have, as long as you can do algebra, it doesn't matter.

Member Avatar for Rashakil Fol

The Akra-Bazzi theorem ( http://en.wikipedia.org/wiki/Akra-Bazzi_method ) applies in this case because sqrt(n) is O(n/log(n)^2) so you can just use the Master theorem. So BestJewSinceJC's intuition is correct.

Member Avatar for anollipian

Try Substitution :P

commented: WTF does that even mean -1
commented: plus i already said that, with a better explanation -1
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.