Is the time complexity of an algorithm calculated only based on the number of loops performed by the loops?
I have great doubts about calculating the time complexity. Is it calculated based on the number of loops the loop does? My question is related to the situation below.
I have a class A that has a String attribute.
class A{
String name;
}
Now I have a list of instances of class A. There are different names in this list. I need to check if the name "Pavan" exists in any of the objects in the list.
Scenario 1:
Here the for loop executes listA.size
times which can be called 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
once.
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 loops for the loop, but I increased the complexity of the logic.
Is it O (n / 2) ? If yes, could you please explain to me?
source to share
First of all, note that there is nothing like Big-O notation O(n/2)
, since it 1/2
is a constant factor that is ignored in these notations. The complexity would remain as O(n)
. So by changing your code, you haven't changed anything in terms of complexity.
In general, an estimate of the number of loops performed in relation to the size of the input and the operation that is actually related to cost over time is the path to the complexity class of the algorithm.
The operation that produces the value in your method is String.equals
that, looking at its implementation, produces the value by comparing characters.
In your example, the size of the input is not strictly equal to the size of the list. It also depends on how large the strings contained in this list are, and how big inputName
.
So let's say the largest string in the list is m1
and the length inputName
is m2
. So, for your original method, the checkName
complexity will come O(n*min(m1,m2))
from String.equals
comparing at most all characters in the string.
For most applications, the term min(m1,m2)
is irrelevant because, for example, one of the compared strings is stored in a fixed-size database column, and therefore this expression is a constant, which, as mentioned above, is ignored.
source to share
The complexity of time and space is calculated based on the number or operations performed, respectively, the number of memory units used.
As for the time complexity: all operations are counted and numbered. Because it is difficult to compare O (2 * n ^ 2 + 5 * n + 3) with O (3 * n ^ 2-3 * n + 1), equivalence classes are used. This means that for very large n values the two previous examples will have approximately the same value (more precisely: they have the same grouth speed). So you shorten the expression to its basic form, saying that the two examples are in the same equivalence class as O (n ^ 2). Likewise, O (n) and O (n / 2) are in the same class and hence both are in O (n).
Due to what I said earlier, you can ignore most of the constant operations (e.g. .size (),. Lenth () on collections, assignments, etc.) as they don't actually count at the end. This way you are left with loops and sometimes complex calculations (somewhere at the bottom of the stack, the loops themselves are used).
For a better understanding of the three complexity classes, try reading articles on the subject, for example: http://discrete.gr/complexity/
source to share
Time complexity is a measure of the theoretical time it will take to complete an operation.
While usually any improvement in the required time is significant in terms of time complexity, we are interested in an order of magnitude. The first means
-
If objects
N
require time slotsN
, then they have complexityO(N)
. -
If the operation for objects
N
requiresN/2
, the complexity is stillO(N)
.
The above paradox is explained, if you want to calculate the operation for large N
, then there is not much difference in part /2
as for part N
. If the complexity O(N^2)
is O(N)
negligible for large N
, so we are interested in the order of magnitude. In other words, any constant is thrown away when calculating complexity.
As for the question, if
Is it calculated based on the number of loops the loop does?
Ok, it depends on what the loop contains. But if only the basic operation is performed inside the loop, then yes. To give an example, if you have a loop that does its own analysis within it, each of which has complexity O(N^3)
, you cannot say that your complexity is simple O(N)
.
source to share
The complexity of the algorithm is measured based on the response made to the size of the input in terms of processing time or space requirement. What I think is missing is that the notation used to express complexity is asymptotic notation.
As per your question, you have decreased the loop execution counter, but not linearly with the size of the input.
source to share