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))
.