Algorithms

Question

Consider the following code fragment 

      

for i=1 to n/2 do
    for j=i to n-1 do
        for k=1 to j do
            output ''foobar''

Assume $n$ is even Let $T(n)$ denote the number of times 'foobar' is printed as a function of $n$.

1. Express $T(n)$ as three nested summations.
2. Simplify the summation. Show your work.

Answer 1

a. $T(n) = \sum_{i=1}^{n/2} \sum_{j=i}^{n-1} \sum_{k=1}^{j} 1$

The 1 is used for constant no. of operations. We can also use $c$ for it.

b. $\sum_{i=1}^{n/2} \sum_{j=i}^{n-1} \sum_{k=1}^{j} 1\\= \sum_{i=1}^{n/2} \sum_{j=i}^{n-1} j\\= \frac{1}{2} \sum_{i=1}^{n/2} (n-1)n - i(i-1) \\= \frac{1}{2} \sum_{i=1}^{n/2} n^2-n - i^2-i $

We need not solve further as the first term itself gives our answer which is $ \frac{n^3}{4}=\Theta\left( n^3\right).$  

PS: In the summation formula for the sum of first $n$ natural numbers $\left( \frac{n.(n+1)}{2} \right)$ and the sum of the squares of first $n$ natural numbers $\left( \frac{n.(n+1).(2n+1)}{6} \right)$ are used.

Comments

Thank u sir..I wasnt able to plot it perfectly. Intuition got me O(n^3).. Thank u again..

---

@Arjun sir Though the output is right there is a mistake in third line of (b). that will be i(i-1) not i(i+1).

---

Thanks, corrected :)

Answer 2

I guess

T(n)  = O(nlogn)

1st loop runs for log n times

2nd loop for log n times

3rd loop for n times

Answer 3

o(n^3).you can easily get a lower tringular matrix by first two loops and 3rd loop is adding another dimension.so its o(n^3).

this type of analysis is not the best method.

Comments

i know the complexity and I have found out.. And the methd is not the right one.. U will get a series. From there u have to calculate.

---

is o(n^3) right answer?

---

Yes O(n³) is correct....

Every inner loop is dependent on outer loop... I mean innermost loop k is dependent on j, and j is dependent on i.... 

outermost loop "i" runs atmost n/2 times. Loop "j" runs atmost n-1 times and innermost loop "k" runs atmost n-1 times....

Altogether it becomes (n/2)*(n-1)*(n-1) = O(n³).