3

I have a big doubt in calculating time complexity. Is it calculated based on number of times loop executes? My question stems from the situation below.

I have a class A, which has a String attribute.

class A{

    String name;
}

Now, I have a list of class A instances. This list has different names in it. I need to check whether the name "Pavan" exist in any of the objects in the list.

Scenario 1:

Here the for loop executes listA.size times, which can be said as O(n)

public boolean checkName(List<String> listA, String inputName){

    for(String a : listA){
        if(a.name.equals(inputName)){
            return true;
        }
    }
    return false;
}

Scenario 2:

Here the for loop executes listA.size/2 + 1 times.

public boolean checkName(List<String> listA, String inputName){

    int length = listA.size/2
    length = length%2==0 ? length : length + 1
    for(int i=0; i < length ; i++){
        if(listA[i].name.equals(inputName) || listA[listA.size - i - 1].name.equals(inputName)){
            return true;
        }
    }
    return false;
}

I minimized the number of times for loop executes, but I increased the complexity of the logic.

Can we say this is O(n/2)? If so, can you please explain me?

Mario Cervera
  • 671
  • 1
  • 8
  • 19
Pavan
  • 337
  • 1
  • 4
  • 10
  • 1
    Firstly, there is no complexity like O(n/2), we generalize it and say O(n). i.e linear. – Prakhar Asthana Dec 03 '14 at 07:34
  • If you require more explanation please clarify. As function with complexities n,n/2,2n are considered as O(n) as the Big O notation is represented as O(n) for linear growth comprises of k(n)+c, here k is any constant form. – Prakhar Asthana Dec 03 '14 at 07:37
  • See [this question](http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o) for a proper explanation of time complexity. – Vincent van der Weele Dec 03 '14 at 07:37

5 Answers5

1

No. In big O expression, all constant values are ignored. We only care about n, such as O(n^2), O(logn).

Min Fu
  • 789
  • 1
  • 6
  • 16
1

Time and space complexity is calculated based on the number or operations executed, respectively the number the units of memory used.

Regarding time complexity: all the operations are taken into account and numbered. Because it's hard to compare say O(2*n^2+5*n+3) with O(3*n^2-3*n+1), equivalence classes are used. That means that for very large values of n, the two previous example will have a roughly similar value (more exactly said: they have a similar rate of grouth). Therefor, you reduce the expression to it's most basic form, saying that the two example are in the same equivalence class as O(n^2). Similarly, O(n) and O(n/2) are in the same class and therefor both are in O(n).

Due to what I said before, you can ignore most constant operations (such as .size(), .lenth() on collections, assignments, etc) as they don't really count in the end. Therefor, you're left with loop operations and sometimes complex computations (that somewhere lower on the stack use loops themselves).

To better get an understanding on the 3 classes of complexity, try reading articles on the subject, such as: http://discrete.gr/complexity/

Adrian B.
  • 1,592
  • 1
  • 20
  • 38
1

First note that in Big-O notation there is nothing such as O(n/2) as 1/2 is a constant factor which is ignored in this notation. The complexity would remain as O(n). So by modifying your code you haven't changed anything regarding complexity.

In general estimating the number of times a loop is executed with respect to input size and the operation that actually is associated with a cost in time is the way to get to the complexity class of the algorithm.

The operation that is producing cost in your method is String.equals, which by looking at it's implementation, is producing cost by comparing characters.

In your example the input size is not strictly equal to the size of the list. It also depends on how large the strings contained in that list are and how large the inputName is.

So let's say the largest string in the list is m1 characters and the inputName is m2 characters in length. So for your original checkName method the complexity would be O(n*min(m1,m2)) because of String.equals comparing at most all characters of a string.

For most applications the term min(m1,m2) doesn't matter as either one of the compared strings is stored in a fixed size database column for example and therefore this expression is a constant, which is, as said above, ignored.

SpaceTrucker
  • 13,377
  • 6
  • 60
  • 99
0

Time complexity is a measure for theoretical time it will take for an operation to be executed.

While normally any improvement in the time required is significant in time complexity we are interested in the order of magnitude. The former means

  • If an operation for N objects requires N time intervals then it has complexity O(N).

  • If an operation for N objects requires N/2 it's complexity is still O(N) though.

The above paradox is explained if you get to calculate the operation for large N then there is no big difference in the /2 part as for the N part. If complexity is O(N^2) then O(N) is negligible for large N so that's why we are interested in order of magnitude. In other words any constant is thrown away when calculating complexity.

As for the question if

Is it calculated based on number of times loop executes ?

well it depends on what a loop contains. But if only basic operation are executed inside a loop then yes. To give an example if you have a loop inside which an eigenanaluysis is executed in each run, which has complexity O(N^3) you cannot say that your complexity is simply O(N).

Eypros
  • 5,370
  • 6
  • 42
  • 75
0

Complexity of an algorithm is measured based on the response made on the input size in terms of processing time or space requirement. I think you are missing the fact that the notations used to express the complexity are asymptotic notations.

As per your question, you have reduced the loop execution count, but not the linear relation with the input size.

codedoc
  • 2,079
  • 2
  • 11
  • 15