## Issue

I am stuck on the analysis of the runtime complexity of my solution to a class problem.

I have a big array that represents a server and each element of the array represents a terminal line. The terminal line holds many users and its count. My job is to read a file that contains a string of numbers and characters on each line, store them in the array, and find the user with the highest count on each terminal line.

However, I have a hard time determinate the time complexity of my solution (LineReport class).

`Analyze the big-O CPU performance of LineReport, for N input lines and O(N) different users, and thus O(N) entries on each list once partially done. `

```
public class LineReport {
private LineUsage[] lines = new LineUsage[501];
private String lineInfo = "";
private int lineNum = 0;
/**
* reads a file once per line via command line, splits each line of string
* into two parts, line number and username, and feeds the username into
* an array of LineUsage object with line number as the index of array.
*/
public void readMessages() {
Scanner scan = new Scanner(System.in);
while(scan.hasNextLine()) {
lineInfo = scan.nextLine();
String[] temp = new String[2];
temp = lineInfo.split(" ");
lineNum = Integer.parseInt(temp[0]);
if (lines[lineNum] != null) {
lines[lineNum].addObservation(temp[1]);
} else {
lines[lineNum] = new LineUsage();
lines[lineNum].addObservation(temp[1]);
}
}
scan.close();
}
/**
* writes the most common user of each terminal line with its count
* to console in following format:<br>
* Line# Username Count<br>
* 1   joe     100
*/
public void showReport() {
System.out.println("Line Most Common User Count:\n");
for (int i = 1; i < lines.length; i++) {
if (lines[i] != null) {
Usage maxUsage = lines[i].findMaxUsage();
System.out.println((i) + " " + maxUsage.getUsername() + " " + maxUsage.getCount());
} else {
System.out.println((i) + " NONE 0");
}
}
}
}
```

```
public class LineUsage {
private Map<String, Integer> users;
LineUsage() {
this.users = new HashMap<String, Integer>();
}
/**
* inserts given string of username into map
*/
public void addObservation(String username) {
if (username.length() > 40) {
throw new IllegalArgumentException("username must be no more than 40 characters");
}
if (users.containsKey(username)) {
users.put(username, users.get(username) + 1);
} else {
users.put(username, 1);
}
}
/**
* iterates through map and find the user with highest count and returns
* an instance of Usage object with found user and its count
* @return the instant of Usage object with found user and its count
*/
public Usage findMaxUsage() {
String maxUser = "";
int maxCount = 0;
for (String username: users.keySet()) {
if (users.get(username) > maxCount) {
maxUser = username;
maxCount = users.get(username);
}
}
return new Usage(maxUser, maxCount);
}
}
```

It seemed to me that this is a O(n^2) solution. It has two methods `readMessages()`

and `showReport()`

. `readMessages()`

has a while loop and a O(n) method `split()`

* so that’s `n * n = n^2`

. `showReport()`

also has loop and a O(n) method `addObservation()`

that’s another `n * n = n^2`

. Therefore, the whole class is `n^2 + n^2 = 2n^2`

. Drop off the constant and I have a complexity of `O(n^2)`

Please correct me if I am wrong on anything.

Thanks in advance.

*https://softwareengineering.stackexchange.com/a/331951

## Solution

The time complexity of `LineReport`

class is **not** `O(n^2)`

. The time complexity of both the methods `showReport()`

and `readMessages()`

is `O(n)`

.

The `split(String regex)`

has a time complexity of `O(n)`

where *N is the number of characters in the input string*. In your case, ** N is not that**,

*. In the*

`N`

is the number of input strings; each such string consisting of line number and username`split()`

function you pass each such string as a parameter.Hence, the complexity of your `split()`

method is **not** O(n). It will be `O(k)`

where *k is the number of characters in the input string*(not `n`

since `n`

already represents something else in your case). Hence the overall complexity of your `readMessages()`

method is `O(n*k)`

.

However if the number characters does not exceed a certain limit say 100 (which is true in your case since the username cannot have more than 40 characters and line number will hardly consist of k digits), then your complexity of split function will be O(100) which will reduce to O(1). To simplify, *if k will not exceed a particular constant no matter what the input n is, then the complexity will reduce to O(n)*.

The time complexity of the method `showReport()`

is O(n). In the `showReport()`

method, there is a `for loop`

which will run for `n times`

. In iteration of the for loop, there is a call to the method `findMaxUsage()`

, *which will run as long as there is a entry in your hashMap*.

In order for your `showReport()`

method to have a complexity of O(n^2), the number of keys in **each** hashMap, which represent the number of user in any particular line, should be n. *This is not possible*. Try to think why and you will understand why is the overall complexity of `showReport()`

is `O(n)`

.

I hope I have helped you. Do comment for any further problems or if you are not able to understand why the number of user in any particular line which always be less than n.

Answered By – AKSingh

Answer Checked By – Dawn Plyler (BugsFixing Volunteer)