• Advertisement
Sign in to follow this  

an Algorithm 'BIG O'

This topic is 4248 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi friends, I wanna know that what is the 'BIG O' for below recursive equation ? ----------------- T(n)=1/(4-T(n-1)) T(1)=1/4 ----------------- Thanks,

Share this post


Link to post
Share on other sites
Advertisement
This looks a bit like a homework question...

'Big O' answers the question "How does the size of the input affect running time?"
An approach you could use to get the hang of it:

If n=1, how many chunks of work do I have to do?
If n=2, how many chunks of work do I have to do?
...
[understand the pattern]
...
in the general case
If n=n, how many chunks of work do I have to do? (a function of n, eg "2n2 - 1")

When you have that, stick it in an O(___), chopping off the irrelevant bits if need be.

Share this post


Link to post
Share on other sites
I understand your mean.
But i want this evaluation big O.(for example O(n*log(n)).
Can you help about this problem ?
Thanks.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
O(1)

Actually, O(2 - √3), which is the same thing.


Eh, why is it constant? It grows linearly ( O(N) ).
T(1) = 1 call to T
T(2) = 2 calls to T
T(3) = 3 calls to T
T(n) = n calls to T

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
Quote:
Original post by ToohrVyk
O(1)

Actually, O(2 - √3), which is the same thing.


Eh, why is it constant? It grows linearly ( O(N) ).
T(1) = 1 call to T
T(2) = 2 calls to T
T(3) = 3 calls to T
T(n) = n calls to T


Silly me, I thought T(n) was the time required to compute the solution for n, as opposed to the actual solution.

Well, T(n) converges toward 2 - √3, if that is any help.

EDIT: then the answer is O(log n) using 2x2 matrix fast exponentiation! [grin]

Share this post


Link to post
Share on other sites
Let f(x) = 1/(4-x). Then:

f(a/b) = 1/(4-a/b) = b/(4b-a) and T(n) = f n(1/4)

We can express f as a 2x2 matrix M:


[ 0 1 ]
M = [ ]
[ -1 4 ]


The above means that M [a;b] = [b; 4b-a], so:

[x;y] = Mn [1; 4] is equivalent to x/y = f n(1/4) = T(n)

Therefore, we need to compute M n and multiply it by [1; 4] to get T(n). And fast exponentiation allows this in O(log n), as you already know.

EDIT + DISCLAIMER: this is not what the exercise is meant to teach you.

Share this post


Link to post
Share on other sites
For solving recurrence relations (it really sucks), there's the master method and the Akra-Bazzi method available for certain classes (wikipedia them or something) but I don't think either will apply here. For more general cases you can solve using generating functions. To the person who solved it above, what method did you use?

Share this post


Link to post
Share on other sites
Quote:
Original post by Zekeva
To the person who solved it above, what method did you use?


I used the fact that 2x2 matrix multiplication is O(1), and that fast exponentiation allows to compute x n in O(log n) multiplications.

Of course, the latter is common knowledge, but you can compute it using the master theorem if you really want to.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
Quote:
Original post by Zekeva
To the person who solved it above, what method did you use?


I used the fact that 2x2 matrix multiplication is O(1), and that fast exponentiation allows to compute x n in O(log n) multiplications.

Of course, the latter is common knowledge, but you can compute it using the master theorem if you really want to.


You are quite dangerous for my brain.

Share this post


Link to post
Share on other sites
Thanks dear friends,
I think that ToohrVyk don't use a famous method for solve this problem.
In university we learned about 6 methods to solve recursive relations,but
i don't familiar with your method.
For example two methods included :
1-Change variable
2-Recursion tree

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement