Home > Software design >  Calculating Time Complexity and Big-O Notation
Calculating Time Complexity and Big-O Notation

Time:01-02

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.

CodePudding user response:

Ignoring the while (true) loop as well as the user input and 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)).

  • Related