Jump to content
  • Advertisement
Sign in to follow this  
mojtaba_e

an Algorithm 'BIG O'

This topic is 4342 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!