an Algorithm 'BIG O'
Author
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,
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.
'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.
Author
I understand your mean.
But i want this evaluation big O.(for example O(n*log(n)).
Can you help about this problem ?
Thanks.
But i want this evaluation big O.(for example O(n*log(n)).
Can you help about this problem ?
Thanks.
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
Quote:Original post by CTarQuote: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]
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:
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.
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.
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?
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
