Is time complexity of an algorithm calculated only based on number of times loop excecutes?

Question

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?

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