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