Stephen Manderson

asked on

# Algorithims & Complexity (Big O) and Sum count

Hi All

I need to calculate the number of times the sum is incremented with respect to the problem size n and give the Big O of the running time.

1.

int sum = 0;

int n = Some_Value;

for (int i=0; i<n*2; i++)

sum++;

for (j=0; j<n; j++)

sum++;

2.

int sum = 0;

int n = Some_Value;

for (int i=0; i<n/2; i++)

for (j=0; j<n*n; j++)

sum++;

3.

int sum = 0;

int n = Some_Value;

for (int i=0; i<n; i++)

for (j=0; j<i; j++)

sum++;

So would the following be correct ?

With regards to sum increment.

1. (n^2) + n

2. (n/2) x (n^2)

3. ? unsure on this one

With regards to the Big O

1. O(n^2) due to the outer loop O(n) and the inner loop is O(n).

2. O(n^3) due to the outer loop O(n) and the inner loop is O(n^2).

3. O(n) due to only O(n) comparisons in the outer loop.

Many Thanks

Steve

I need to calculate the number of times the sum is incremented with respect to the problem size n and give the Big O of the running time.

1.

int sum = 0;

int n = Some_Value;

for (int i=0; i<n*2; i++)

sum++;

for (j=0; j<n; j++)

sum++;

2.

int sum = 0;

int n = Some_Value;

for (int i=0; i<n/2; i++)

for (j=0; j<n*n; j++)

sum++;

3.

int sum = 0;

int n = Some_Value;

for (int i=0; i<n; i++)

for (j=0; j<i; j++)

sum++;

So would the following be correct ?

With regards to sum increment.

1. (n^2) + n

2. (n/2) x (n^2)

3. ? unsure on this one

With regards to the Big O

1. O(n^2) due to the outer loop O(n) and the inner loop is O(n).

2. O(n^3) due to the outer loop O(n) and the inner loop is O(n^2).

3. O(n) due to only O(n) comparisons in the outer loop.

Many Thanks

Steve

ASKER CERTIFIED SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**SOLUTION

membership

Create a free account to see this answer

Signing up is free and takes 30 seconds.

**No credit card required.**ASKER

Ahh i see :)

Thanks

Thanks

ASKER

Thanks

Ouch! Can't believe I missed that... Thanks, ozo.

(°v°)

(°v°)

ASKER

Yup think you are right for #1 ozo

Regards

Steve