Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am just looking for basic step by step in how to turn a pseudo code algorithm into a function and then how to calculate and show T(n) ∈ O(f(n)), and that T(n)∈ Sigma(f(n))

Also if someone could really explain to me in plain engish, that would be great. I'm not so good at understanding the meaning of some symbols. T(n) ∈ O(f(n)) iff ∃ c > 0, n0 > 0 such that T(n) ≤ cf (n) for n > n0

example pseudo code:

sum = 0;
for(int i=0; i < N ;i++)
  for(int j=0; j < i*i ;j++)
    for(int k=0; k < j ;k++)
     sum++;

please don't just write the answer to it. I already know that the answer is T(n)∈ O(n^5), but I need to know how to get that answer.

share|improve this question

2 Answers 2

Basically we just want to count the number of times we execute the innermost instruction, the sum++ instruction. The innermost for loop executes it $j$ times. However, this loop runs for each value of $j$ from $0$ through $i^2-1$. Thus, for each fixed value of $i$ the sum++ instruction is executed

$$0+1+2+3+\ldots+\left(i^2-1\right)=\sum_{j=0}^{i^2-1}j=\frac12i^2\left(i^2-1\right)\tag{1}$$

times. (For that last step I’ve used the well-known formula for the sum of consecutive integers.)

Finally, the middle for loop runs for each value of $i$ from $0$ through $N-1$, so to find how often the sum++ instruction is executed, we must substitute values of $i$ from $0$ through $N-1$ into $(1)$ and add up the results. That gives us

$$\frac12\cdot0^2\left(0^2-1\right)+\frac12\cdot1^2\left(1^2-1\right)+\frac12\cdot2^2\left(2^2-1\right)+\ldots+\frac12\cdot(N-1)^2\left((N-1)^2-1\right)\;,$$

or $$\sum_{i=0}^{N-1}\frac12i^2\left(i^2-1\right)=\frac12\sum_{i=0}^{N-1}i^2\left(i^2-1\right)=\frac12\left(\sum_{i=0}^{N-1}i^4-\sum_{i=0}^{N-1}i^2\right)\;.\tag{2}$$

Formulas for the last two summations in $(2)$ are known $-$ most any calculus book has the formula $$\sum_{i=1}^ni^2=\frac16n(n+1)(2n+1)\;,$$ for instance $-$ but all you really need to know is that for any non-negative integer $k$ the sum $\sum\limits_{i=1}^ni^k$, thought of as a function of $n$, is a polynomial in $n$ of degree $k+1$. This means that $\sum\limits_{i=0}^{N-1}i^4$ is a polynomial in $N-1$ of degree $5$, so after you multiply out all of the powers of $N-1$, you have a polynomial in $N$ of degree $5$. Similarly, $\sum\limits_{i=0}^{N-1}i^2$ is a polynomial in $N$ of degree $3$. Half their difference is a fifth degree polynomial in $N$; say

$$T(N)=\sum_{i=0}^{N-1}\frac12i^2\left(i^2-1\right)=a_0N^5+a_1N^4+a_2N^3+a_3N^2+a_4N+a_5\;.\tag{3}$$

For any $N$, the polynomial in $(3)$ gives the number of times the sum++ instruction is executed. I expect that you’ve seen the theorem that a polynomial of degree $n$ is $O(x^n)$, so you now know why this algorithm is $O(N^5)$.

Intuitively this just means that that there is some constant $C$ such that for all values of $n$ from some point on, $T(n)\le Cn^5$. (That actually should be $|T(n)|\le C|n^5|$, but in this case the absolute values aren’t doing anything, so I’ve omitted them to keep the explanation as uncluttered as possible.) The first $100$ (or $1000$, or $100$ million) values of $T(n)$ might violate the inequality $T(n)\le Cn^5$, but eventually, once $n$ is large enough, it will be true thereafter that $T(n)\le Cn^5$. That’s the purpose of the $n_0$ in the definition: it’s a point beyond which the inequality holds.

To put it very informally, from some point on $T(n)$ grows no faster than some fixed multiple, $C$, of $n^5$: the ratio $\dfrac{T(n)}{n^5}$ is never bigger than $C$ once $n$ is large enough ($n>n_0$), though it might be bigger for some finite number of smaller values of $n$.

share|improve this answer

A little more intuitively:

The basic idea is that $\sum_{i=0}^{m-1} i^k = \dfrac{m^{k+1}}{k+1}+O(m^k) \approx \dfrac{m^{k+1}}{k+1} $. For these types of estimates (where there are no subtractions that might cause significant cancellation), this high order term is almost always all that is needed.

The inner loop is done j times.

The next loop is done $i^2$ times of the inner loop. This is $\sum_{j=0}^{i^2-1} j \approx \dfrac{(i^2)^2}{2} = \dfrac{i^4}{2} $.

The outermost loop is done $N$ times of the next loop. This is $\approx \sum_{i=0}^{N-1}\dfrac{i^4}{2} = \frac1{2}\sum_{i=0}^{N-1} i^4 \approx \frac1{2} \dfrac{N^5}{5} = \dfrac{N^5}{10} $.

You can reasonably conclude from this that $sum \approx \dfrac{N^5}{10}$ with an error of order $N^4$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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