# Theta estimation of two functions

I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and everything I can find online expects more prior knowledge than I feel I have. Can someone just explain this in beginners terms for me? I don't know what Big-O or theta even refer to in this notation. I think I have a loose idea of what "complexity" refers to (a measure of how efficient code is, depending on how long a function will take in different circumstances?)

The problem in question:

Demonstrate the $\Theta$-complexity of the functions below. In order to demonstrate that $f(n) = \Theta(g(n))$ you must find two constants $C_1$ and $C_2$ such that $$C_1g(n) ≥ f(n) ≥ C_2g(n).$$

a.) $f(n) = n^3 - 3n^2 + 5$.

b.) $f(n) = 2\log_2 n - 4$.

The exercise being asked about is pretty stupid (this is criticism against the person who set it as an exercise, not the OP). Every (positive) function $f$ is its own big $\Theta$, that is $f(n) = \Theta(f(n))$. Nevertheless, whoever asked the question expected the following answers: $f(n) = \Theta(n^3)$ and $f(n) = \Theta(\log n)$. There are many online and offline resources that can explain why this is the case and how to prove it, or you can try working through the algebra yourself.

Please let the poser know that the following answers are as mathematically correct as the expected one: $n^3 - 3n^2 + 5 = \Theta(17n^3 - 2n\log n + 4\log\log n)$ and $2\log_2 n - 4 = \Theta(4\log_4 n - 2)$. In order to rule out these answers, the poser should have phrased the question as follows:

For each of the following functions $f(n)$, find a function $g(n)$ of the form $n^\alpha (\log n)^\beta$ such that $f(n) = \Theta(g(n))$, and prove that $f(n) = \Theta(g(n))$.

Note that in general a function $g(n)$ of that specific form might not exist, for example if $f(n) = n\log\log n$, or for the following more exotic function: $$f(n) = \begin{cases} n & \text{ if n is odd,} \\ n^2 & \text{ if n is even.} \end{cases}$$ Such functions nearly show up in modular exponentiation, FFT-based algorithms, and fast matrix multiplication, though in these cases the difference is only in the constant (e.g. $n$ vs. $2n$) rather than the asymptotics.

• "There are many online and offline resources that can explain why this is the case and how to prove it" -- Yes, for instance here.
– Raphael
Nov 10 '14 at 11:33

The Complexity of an algorithm is the behavior that it have in memory or time (execution). This means that, for example, if you have an algorithm to explore a matrix of dimensions nxn to find a number, then the algorithm have a Complexity equals to Big-O(n^2). This because, in the worst case, you need to explore the nxn locations of the matrix. The theta complexity, refers to algorithms that have an exact behavior, i.e., if you have an algorithm to explore everyone of the locations of a Matrix with nxn dimension, that algorithm have a Complexity Theta(n^2), because you are exploring (no more, no less) the complete matrix nxn.

• Unfortunately, this answer is wrong in several ways. Complexity is a measure of problems, not algorithms. $O()$ and $\Theta()$ are measures of functions, not algorithms. $O()$ provides an upper bound on a function: that function could be used to describe the worst-case running time of an algorithm, or used for anything else, such as the best case. Nov 10 '14 at 8:52