CODEWITHSUNDEEP
javabig-o
umtkas
umtkas

Reputation: 62

Java Big O notation in algorithm

i am comfused with this big O notation problem. This code does not look like O(n) but for loop turns number of word time so it is basically not more than 20 so, if we say Length (line.split()) is constant c, can we say O(c.n) = O(n) ?

while (this.scannerMainText.hasNextLine()){
        String line = this.scannerMainText.nextLine();
        for (String word : line.split("[.!,\" ]+")) {
           some statements
         }
     }

Upvotes: 0

Views: 340

Answers (2)

Matt Mills
Matt Mills

Reputation: 8792

Yes.

Time complexity is based only on the number of times an algorithm is run; the actual number/cost of steps within the algorithm (c, as you call it) is not considered for Big-O notation.

Added

I'm not familiar enough with the edge cases of the theory to say that if all of the lines are equal in length you can reduce the runtime of the inner loop to a constant. In general, this algorithm would be considered O(mn).

Upvotes: 2

Jeffalee
Jeffalee

Reputation: 1085

Yes, the amount of times a loop is run has a negligible impact on the duration, therefore it is usually not mentioned in the Big-O notation.

For example, if a O(n) loop is run 20 times, you would think the notation would be O(20n), but because the impact is so small it is not mentioned it the Big-O notation and therefore O(20n) = O(n). Same goes for O(20n²) = O(n²) etc..

Upvotes: 2

Related Questions