0
$\begingroup$

I have solved that the recurrence of running time of the algorithm given as

$$ T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases} $$

So the question is that solve the recurrence that I have solved above.

So this is my answer.

Case 1

Show that $T(n) = \Theta(n)$

Guess $T(n) \le dn^2 $

$T(n) \le d(n-1)^2 + cn$

$ = d(n^2-2n+1)+cn $

$ = dn^2 - (2d-c)n + d $

it solves when $d \ge (2d-c) n $, which is same as $ \frac{d}{2d-c} \ge n $

When $ \frac{d}{2d-c} \ge n $ , then $T(n) = O(n^2) $


So this process is equally in Case 2 which is showing $T(n) = \Omega (n^2)$.

Can you please check whether my approach is right?

Thanks for your help.

$\endgroup$
  • 2
    $\begingroup$ Sorry, but it's not the mission of this site to check your work. Rather than a command, we'd like a question. Help us to help you: why do you need an independent source to verify your work, except perhaps that you think it's wrong. Here comes the question: why do you think it's wrong? $\endgroup$ – Rick Decker Apr 17 at 23:25
0
$\begingroup$

Why do u need to guess? T(n) = T(n-1) + cn {c is a const} T(n) = T(n-2) +c(n-1) +cn = T(n-3) +c*[(n-2)+ (n-1) + n] .....

Keep going this way till u reach the arithmetic sequence (2+...+(n-1)+n]. So,

T(n) = T(1) + c* n(n-1)/2 = O(n2)

You may check any Algorithms book or lecture notes on solving recursive equations; we don't usually guess, there r rules and this one is trivial.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.