Big oh problem

**Acessd23** · October 15th 2009, 10:16 PM

I couldn't solve this one ?

What is the Big O of this function ?

Void two(int n)
{
int

i,j,k,n;

for

(i=1;i<=n;i++)
for (j=(i+1);j<=n;j++)
for (k=1;k<=j;k++)

o(1) statment;
}

**CaptainBlack** · October 15th 2009, 10:39 PM

Originally Posted by Acessd23

I couldn't solve this one ?

What is the Big O of this function ?

Void two(int n)
{
int

i,j,k,n;

for

(i=1;i<=n;i++)
for (j=(i+1);j<=n;j++)
for (k=1;k<=j;k++)

o(1) statment;
}

The loop operations count of the inner most loop is $o(1)j$ , so that of the next outer loop is:

$\sum_{j=i+1}^n o(1)j$

ans so for the outermost loop:

$\sum_{i=1}^n \left[ \sum_{j=i+1}^n o(1)j\right]=o(1)\sum_{i=1}^n \left[ \sum_{j=i+1}^n j\right]$

CB

Thread: Big oh problem

LinkBack

Thread Tools

Display

Big oh problem

Search Tags