CODEWITHSUNDEEP
c
Coder333
Coder333

Reputation: 53

What is the time complexity of this code, and could you explain how you calculated it?

The code below I found the time complexity to be n^2 if that is correct?

int numbers[9] = {1, 5, 7, 8, 9, 14, 21};
int check = 50;

int count = 0;
for (int i = 0; i < 9; i++) {
    int squared = numbers[i]*numbers[i];
    int target = check - squared;
    for (int j = i; j < 9; j++) {
        if (numbers[j]*numbers[j] == target) {
            count++;
        }
    }
}
if (count == 2) {
    printf("Yes\n");
} else {
    printf("No\n");
}
return 0;

Upvotes: 0

Views: 81

Answers (3)

caot
caot

Reputation: 3328

It can be understood in such a way:

Change the 9 into int n = 9;, and

for i = 0,   inner loop 0, 1, 2, ...., n - 1
for i = 1,   inner loop    1, 2, ...., n - 1
for i = 2,   inner loop       2, ...., n - 1
......
for i = n-1, inner loop                n - 1

So all of operation takes about n * n / 2 = O(n^2)

The Big O notation might be helpful.

Upvotes: 1

Wootiae
Wootiae

Reputation: 848

I think your input data is numbers[n] where n = 9.

Simple instructions

The last part of algorithm:

if (count == 2) {
    printf("Yes\n");
} else {
    printf("No\n");
}
return 0;

This code is O(1), printf, if-else, return aren't scale with numbers.

These lines (were taken out of context) have O(1) for the same reason.

int numbers[9] = {1, 5, 7, 8, 9, 14, 21};
int check = 50;

int count = 0;

int squared = numbers[i]*numbers[i];
    int target = check - squared;

if (numbers[j]*numbers[j] == target) {
    count++;
}

Everything that doesn't scale with input data has O(1).

Loops make complexity

for (int i = 0; i < n; i++) {
    // task
}

Common loop runs task n times and it means that the complexity of this loop is O(N) * complexity(task).

In your algorithm are nested loops and it means.

int k = n;
for (int i = 0; i < n; i++) {
    for (int j = i; j < k; j++) // task
        O(1);
}

Task's complexity is O(k * 1) = O(k) = O(n).

Loop's complexity is O(n * complexity(task)) = O(n * k) = O (n^2)

Upvotes: 0

ssoBAekiL
ssoBAekiL

Reputation: 635

Yes, the worst case time complexity will be O(n^2), with n obviously being the length of the array.

To find the time complexity of any code you need to count how many times is executed the most recurrent function in your code. In this case that is the comparison numbers[j]*numbers[j] == target. After finding that the math in this case is easy, the outer loop is executed up to n times (in this case hardcoded to 9, not recommended), and for each of those times the inner loop is executed up to n times resulting in a worst case time complexity of O(n^2).

If you're also interested in the best case time complexity it's still O(n^2) but it can be easily be dropped to 2.

Upvotes: 0

Related Questions