Big oh problem - Math Help Forum

$Math Help Forum$

$Go Back$		Math Help Forum > University Math Help > Other Advanced Topics
$Reload this Page$ Big oh problem

Download MHF Flyer

Mark Forums Read

$Reply$

#1

$Old$ October 16th, 2009, 12:16 AM

Acessd23 $Acessd23 is offline$

Newbie

Join Date: Oct 2009

Posts: 3

Thanks: 0

Thanked 0 Times in 0 Posts

$Acessd23 is on a distinguished road$

$Default$ Big oh problem

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;
}

$Reply With Quote$

Advertisement

#2

$Old$ October 16th, 2009, 12:39 AM

$CaptainBlack's Avatar$

$CaptainBlack is offline$

Grand Panjandrum

Join Date: Nov 2005

Location: South of England

Posts: 11,379

Country:

United Kingdom

Thanks: 667

Thanked 3,619 Times in 2,916 Posts

$CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$ $CaptainBlack has a reputation beyond repute$

$Default$

Quote:

Originally Posted by Acessd23 $View Post$

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

__________________
Truth does not change because it is, or is not, believed by a majority of the people.

Giordano Bruno

$Reply With Quote$

$Reply$

« Big oh problem #2 | Top | Z transform of a periodic function »

Thread Tools
$Show Printable Version$ Show Printable Version $Email this Page$ Email this Page
Display Modes
$Linear Mode$ Linear Mode $Hybrid Mode$ Switch to Hybrid Mode $Threaded Mode$ Switch to Threaded Mode

Posting Rules
You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are Off

Forum Jump

All times are GMT -7. The time now is 04:20 PM.

your link here Sponsors

rv solar, e-learning,

Math Help Forum is a community of maths forums with an emphasis on maths help in all levels of mathematics.
Register to post your math questions or just hang out and try some of our math games or visit the arcade.