# an Algorithm 'BIG O'

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

## 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 on other sites
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 on other sites
But i want this evaluation big O.(for example O(n*log(n)).
Thanks.

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

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

##### 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 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 on other sites
Are you sure ?!?!? [tears]

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

1. 1
2. 2
3. 3
Rutin
22
4. 4
5. 5

• 13
• 19
• 14
• 9
• 9
• ### Forum Statistics

• Total Topics
632930
• Total Posts
3009289
• ### Who's Online (See full list)

There are no registered users currently online

×