0
$\begingroup$

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$.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ "There are many online and offline resources that can explain why this is the case and how to prove it" -- Yes, for instance here. $\endgroup$
    – Raphael
    Commented Nov 10, 2014 at 11:33
-1
$\begingroup$

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.

This is very abstract, I recommend you read about Asymptotic analysis

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Commented Nov 10, 2014 at 8:52
  • $\begingroup$ Thanks a lot to show me that the earth isn't plane... If you, Einstein, read again the question can note this "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 just show this topics in simple way as possible. $\endgroup$
    – Yunrock
    Commented Nov 10, 2014 at 20:39
  • 2
    $\begingroup$ I'm sorry but the simplest possible way to explain anything has to be a correct explanation. An explanation that is simple but wrong is not useful. $\endgroup$
    – David Richerby
    Commented Nov 10, 2014 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.