Link to home
Create AccountLog in
Avatar of Stephen Manderson
Stephen MandersonFlag for United Kingdom of Great Britain and Northern Ireland

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
ASKER CERTIFIED SOLUTION
Avatar of Markus Fischer
Markus Fischer
Flag of Switzerland image

Link to home
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
See answer
SOLUTION
Avatar of ozo
ozo
Flag of United States of America image

Link to home
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
Avatar of Stephen Manderson

ASKER

With regards to the Big O for the 3rd loop would it not be the case that it would be O(n) with respect to n as there is no n in the inner loop?

Yup think you are right for #1 ozo

Regards
Steve
SOLUTION
Link to home
membership
Create a free account to see this answer
Signing up is free and takes 30 seconds. No credit card required.
Ahh i see :)

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

(°v°)