2
$\begingroup$

This question already has an answer here:

I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application.

I understand that if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$ then $f(n) \in \Theta(g(n))$

Essentially, when Big-O and Big-Omega form the upper and lower bounds of algorithmic performance, Big-Theta represents the optimal solution. But how does one determine those bounds and thus optimal performance?

How does/should one determine Big-O, Big-Omega, Big-Theta for the following algorithm?

int summation(int[] values)
{
  int sum = 0;
  for(int i = 0; i < values.length; i++)
  {
    sum += values[i];
  }
}
$\endgroup$

marked as duplicate by Raphael Mar 29 '14 at 11:47

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $\Theta(-)$ says nothing about optimality: it's just a measure of the rate of growth of a function. For example, the worst-case running time of bubble sort on a list of $n$ items scales as $\Theta(n^2)$. That doesn't say that bubble sort is optimal (it isn't!), or that the worst case is the optimal case (it isn't!); it just gives tight bounds on how long it takes to run in the worst case. You could also measure the best-case running time of bubble sort in terms of $\Theta(-)$. Or the average case (given some probability distribution on the inputs). $\endgroup$ – David Richerby Mar 28 '14 at 23:46
  • $\begingroup$ The property of Landau notation has nothing to do with runtime analysis. (It is used there, though.) As it is, this question is answered by our reference question or many similar algorithm-analysis questions. $\endgroup$ – Raphael Mar 29 '14 at 11:46
1
$\begingroup$

Typically, when presented with a piece of code, your first step is to come up with a formula which gives the running time $T$ of your code as a function of the input size. In your example, the function takes an array, so a natural way to represent the input size is the number of elements in the array, values.length, which we can call $n$.

So, we now want an expression for $T(n)$. To get this, we should assign a "cost" to each statement, and then determine how many times each statement is executed. The costs are somewhat arbitrary and may vary across real computer hardware, but some assumptions can reasonably be made; in particular, we usually assume simple statements have a constant cost with respect to the input size. In your example, we might assign costs like this:

int summation(int[] values)
{
  int sum = 0;                       // cost = A, executed once
  for(int i = 0;                     // cost = B, executed once
      i < values.length);            // cost = C, executed n + 1 times
      i++)                           // cost = D, executed n times
  {
    sum += values[i];                // cost = E, executed n times
  }
}

Now, to get the expression for $T(n)$, multiply each statement's cost by the number of times it's executed. Here, we get $T(n) = A \times 1 + B \times 1 + C \times (n + 1) + D \times n + E \times n$. This comes out to $T(n) = (A + B + C) + (C + D + E) \times n = c_0 + c_1n$ for constants $c_0, c_1$.

In this example, happily, we have a closed-form expression for $T(n)$. As such, we can make an educated guess that this function is $\Theta(n)$, since $T(n)$ is a linear function. To prove this is true, we can try to prove it's both $\Omega(n)$ and $O(n)$.

By definition, $T(n) = \Omega(n) \iff \exists c > 0, n_0 \ge 0 \mid n \ge n_0 \rightarrow T(n) \ge cn$. Our job now is to demonstrate that there is an $n_0$ and $c$ such that $T(n) \ge cn$ for all $n \ge n_0$. We have $c_0 + c_1n \ge cn$ for fixed constants $c_0, c_1$. We can solve this for $c$: $c \le c_0/n + c_1$. As long as we choose $c$ less than $c_0/n + c_1$, we have a valid choice for $c$; in particular, if we choose $c = c_1$, we satisfy the inequality for all natural numbers, and can choose $n_0 = 0$.

You can make a very similar argument for $O$; try choosing $c = c_0 + c_1$ in this case and complete the argument yourself. Once you know it's both $\Omega(n)$ and $O(n)$, you can conclude that it's $\Theta(n)$.

Of course, you don't really need to find the constants every time, but it can make an argument pretty convincing. If your $T(n)$ comes out to a expression which is the sum of powers of $n$, then you will always have that $T(n) = \Theta(n^x)$, where $x$ is the highest power to which $n$ is raised.

This gets significantly harder when $T(n)$ is recursive, i.e., when the expression for $T(n)$ involves $T$ itself; to solve problems like that, you'll often need to avail yourself of the Master Theorem or inductive proofs on the input size. Cross that bridge when you come to it, though.

$\endgroup$
  • $\begingroup$ This may be a nice example for the reference question? $\endgroup$ – Raphael Mar 29 '14 at 11:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.