0

I need help to check whether my ascending sorting code has correct time complexity measurement or not.

Here is my code

for (int i = 0; i < 4344; i++)
{
    for (int j = i + 1; j < 4344; j++)
    {
        if (array_dist[index_arr[i]] > array_dist[index_arr[j]])
        {
            x = index_arr[i];
            index_arr[i] = index_arr[j];
            index_arr[j] = x;
        }

    }
}

We have two nested loops so N^2 and if statement with 3 operations, so N^2 + 3 then we got O(N^2).

I am not sure if O(N^2) is the correct time complexity for my code. I want to know if the if statement could change my answer?

Improve this question
12
  • Hint: can you construct an input where the if condition is always true? Commented Oct 27, 2021 at 17:41
  • 2
    Since the loops use constants it would be O(1) since the runtime isn't dependent on the length of the input (N). (It's always 4344) Commented Oct 27, 2021 at 17:43
  • 2
    The if is irrelevant here since the content of the if block is O(1). The number of time you execute the inner loop is O(n^2) (assuming you do not have constant bound), regardless of whether you enter the if or not. Entering the if or not (all the time) only multiply this n^2 by a constant, so that's still O(n^2). Commented Oct 27, 2021 at 17:50
  • 1
    @JOJO Yes, the time complexity is O(N^2). Commented Oct 28, 2021 at 11:46
  • 1
    @JOJO However, this part "We have two nested loops so N^2 and if statement with 3 operations, so N^2 + 3 [...]". You have N^2 * 3 (times, not plus), because for every loop you execute 3 operations (assuming you always enter the if), but O(3 * N^2) is O(N^2). Commented Oct 28, 2021 at 11:49
Related questions
53
What is the time complexity of std::sort() in the C++ standard library?
3
What is the complexity of this sorting algorithm?
2
calculating complexity of sorting
Load 7 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.