Run-time analysis, Assignment 3

Although the third assignment's deadline was generously extended, my group-partners and myself went through a number of issues trying to solve the problems.  Among the most difficult questions, in my opinion, was question 5, which asked to prove or disprove that for all functions f and g that take in natural numbers and return real ones, f is in Big-Oh of g, or f is in Big-Theta of g.  Intuition led us to disprove the statement, thus we went ahead and approached the negation of the statement to become:

"There exist functions f and g such that f is not in Big-Oh of g, and  f is not in Big-Theta of g."  Of course aside from everything else, coming up with individual equations which exactly satisfy the statement was a challenging step.  That is, the two functions f and g should grow in such a way that none of them bounds the other.

Our first approach was to construct sine and cosine functions in such a manner that they "oscillate" without ever bounding one another permanently.  Of course, the graph below shows that the idea was plausible however the actual implementation got so tricky with issues ranging from managing the Pi to manipulating variable n properly, that we decided to search for other ways.  

The solution, as it turns out, was not too complex: find two functions which grow in the form of the following, with f shown in blue and g shown in green.

(Courtesy of Google)

Taking two piece-wise functions as f and g, then proving the negation of the original statement was what we resorted to.  Two cases were taken to examine the effect of having odd or even natural numbers used in the process of disproving of Big-Oh and Big-Theta.