Calculating Time Complexity and Big-O Notation

Question

What is the time complexity of my following code in Big-O notation and what are the steps of calculating it?

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        File file = new File("C:\\Users\\yousu\\OneDrive\\سطح المكتب\\textfile\\OptimizeBusInput.txt");
        Scanner scan = new Scanner(file);
        while(true) {
            int n = 0;
            int d = 0;
              int r = 0;
              int outcome = 0;
            
            n = scan.nextInt();
            d = scan.nextInt();
            r = scan.nextInt();

            if ( n + d + r == 0) break;

            int[] morning = new int[n];
            int[] afternoon = new int[n];

            for (int i = 0; i < n; i++) {
                morning[i] = scan.nextInt();
            }
            for (int i = 0; i < n; i++) {
                afternoon[i] = -scan.nextInt();
            }
            Arrays.sort(morning);
            Arrays.sort(afternoon);

            for (int i = 0; i < n; i++) {
                int sum = morning[i] + (-afternoon[i]) - d;
                if (sum > 0) outcome += sum * r;
            }
            System.out.printf("%d\n", outcome);
        }

I have tried calculating the time complexity of every loop and if statement separately but I am not sure how to combine them for the final result. My code follows a Transform & Conquer technique.

Turing85 · Accepted Answer · 2023-01-01T23:00:50.503

0

Ignoring the while (true) loop as well as the user input and analyzing just the part without user interaction, we have two sort-operations on arrays of size n (which is known to be O(n * log(n)) and one loop iterating n times (i.e. O(n)). Thus, the overall complexity is 2 * n * log(n) + n ∈ O(n * log(n)).

edited Jan 01 '23 at 23:00

answered Jan 01 '23 at 20:42

Turing85

18,217
7
33
58

May I ask what would the space complexity also be? Given that we have 2 sort operations, are they in-place or not? – halemley Jan 01 '23 at 22:47
If we again ignore the memory needed for the input (i.e. the two arrays), space complexity should be `O(1)` since the sort is in-place. – Turing85 Jan 01 '23 at 22:50
Just took a peek at the sort algorithm. It is not guaranteed that the space complexity is `O(1)`. There is at least one case I can see where an array is constructed. So worst case, I'd estimate it with `O(n)` space complexity. – Turing85 Jan 01 '23 at 22:58

Calculating Time Complexity and Big-O Notation

1 Answers1