Jump to content
• ### What is your GameDev Story?

• Advertisement

# an Algorithm 'BIG O'

This topic is 4584 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

##### 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

##### 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

##### Share on other sites
O(1)

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

#### Share this post

##### Share on other sites
Quote:
 Original post by ToohrVykO(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

##### Share on other sites
Quote:
Original post by CTar
Quote:
 Original post by ToohrVykO(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

##### Share on other sites
Are you sure ?!?!? [tears]

#### Share this 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

##### 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

##### Share on other sites
Quote:
 Original post by ZekevaTo 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

##### Share on other sites

• Advertisement
• Advertisement
• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• ### Popular Now

• 15
• 10
• 11
• 9
• 9
• Advertisement
• ### Forum Statistics

• Total Topics
634148
• Total Posts
3015794
×

## Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!