The Masters Thm covers only a certain family of recurrences. There
are many others.
Solving recurrences is comparable to finding analytical solutions to
differential equations except that recurrences aren't as important in
mathematical analysis, so aren't studied as much.
I am not an expert, but
Thanx Gene. Is there any other method than master's thm ?
On Nov 23, 4:13 pm, Gene wrote:
> Solving recurrences is an art form. There are many techniques. One
> of the simplest is to assume you know the form of the result with some
> unknown coefficients. Then plug the form into the recurrence
Solving recurrences is an art form. There are many techniques. One
of the simplest is to assume you know the form of the result with some
unknown coefficients. Then plug the form into the recurrence and try
to solve for the coefficients. If you succeed, you're done. If not,
look for another form
Answer (B)
Let n = 2^m, T(n) = T(2^m)
Let T(2^m) = S(m)
>From the above two, T(n) = S(m)
S(m) = 2S(m/2) + C1
Above expression is a binary tree traversal recursion whose time
complexity is (m). You can also prove using Master theorem.
S(m) = (m)
= (logn) /* Since n = 2^m */
Now, let
A friend asked me this question ...
Also asked me another modification ,
T(n) = T[ *mod*(n-2^( ceil(log n) )) ] +O(n)
Can we find the complexity for such a recurrence ?
On Mon, Sep 15, 2008 at 9:17 AM, Ashesh <[EMAIL PROTECTED]> wrote:
>
> You should agree with the fact that log(n-1) <= ceil(l
You should agree with the fact that log(n-1) <= ceil(log(n-1)) <
log(n-1)+1,
which would mean that n-1 <= 2^(ceil(log(n-1))) < 2(n-1), thus, 2-n <
n-2^ceil(log(n-1)) <= 1. Thus, unless 2-n<1, there are no such
possible values. We must therefore have that n>1.
Moreover, as long as the base of the
Actually there is one more condition to it but i thought it will be more
complicated
to mention it,
at each step we subtract 2^(ceil(log n) if n-2^( ceil(log n) ) > 0
else we subtract n-2^( ceil(log (n-1)) )
So,
T(n) = T[ n-2^( ceil(log n) ) ] +O(n)for n-2^( ceil(log n) )>0
= T[ n-2^(
In such a case, ceil(log(n)) > log(n), and if the base of the
logarithm is 2 or less, then 2^(ceil(log(n)) > n, and the question
fails to be valid. The base of the logarithm has to be greater than 2.
On Sep 14, 9:26 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote:
> Sorry i forgot, it is ceil(log n)
Sorry i forgot, it is ceil(log n) so n-2^( ceil(log n) ) is not equal to
zero..
On Sun, Sep 14, 2008 at 8:57 AM, Karthik Singaram Lakshmanan <
[EMAIL PROTECTED]> wrote:
>
> Isn't n-2^logn = 0?
> since 2^logn = n if you are talking about log base 2
>
> >
>
--
Ciao,
Ajinkya
--~--~-~--~-
Isn't n-2^logn = 0?
since 2^logn = n if you are talking about log base 2
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To uns
10 matches
Mail list logo
