Question

Big-O notation.

Consider the following function.

int func1(int n) {

int sum = 0, i;

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

sum += i;

return sum;

}

Express the running time of func1 as a function of n using big-O notation.

Write a function that has the same functionality as func1, but runs in O(1) time.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

Since there is 1 loop over n. So, it is O(n)

The function with O(1) complexity is

int func1(int n) {

int sum = 0, i;

sum=(n)*(n-1)/2;

return sum;

}

Kindly revert for any queries

Thanks.