2 replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/ edited Apr 13 '17 at 12:48 No. There are complexity functions that oscillate, for example runtime of Mergesortruntime of Mergesort. It is not even true that every meaningful complexity function is in $$\Theta$$ of a monotonically increasing function; see this answerthis answer to your older question. No. There are complexity functions that oscillate, for example runtime of Mergesort. It is not even true that every meaningful complexity function is in $$\Theta$$ of a monotonically increasing function; see this answer to your older question. No. There are complexity functions that oscillate, for example runtime of Mergesort. It is not even true that every meaningful complexity function is in $$\Theta$$ of a monotonically increasing function; see this answer to your older question. 1 answered Mar 20 '13 at 21:07 Raphael♦ 58.9k2525 gold badges144144 silver badges327327 bronze badges No. There are complexity functions that oscillate, for example runtime of Mergesort. It is not even true that every meaningful complexity function is in $$\Theta$$ of a monotonically increasing function; see this answer to your older question.