PDA

View Full Version : Algo to determine order relationshio between two functions



nipunreddevil
January 6th, 2010, 04:01 AM
Given two functions f(n) and g(n),what i intend to do is to establish a relation among these as in:
f(n)=O(g(n)) or f(n)=theta(g(n)) etc.What is the most efficient way to do this:
1.Without programming using pen and paper
2.Using programming

jpkotta
January 6th, 2010, 07:41 AM
A general algorithm would solve the Riemann Hypothesis (http://en.wikipedia.org/wiki/Riemann_hypothesis#Consequences_of_the_Riemann_hyp othesis). You have to give specific functions. Also, "most efficient" is a question of how much math you know. I guess a way that would work for "nice" functions is finding lim_{n→∞} f(n)/g(n).