[SOLVED] What is the time complexity of my program?

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 &emsp;&emsp;joe &emsp;&emsp;&emsp; 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, N is the number of input strings; each such string consisting of line number and username. In the 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)

Leave a Reply

Your email address will not be published. Required fields are marked *