Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of the integer that is evaluated as even.How come the algorithm would have 2n+1 comparison?I thought linear search would have n comparision because it is going through n elements. +1 comparison for the if statement. So that would make the algorithm O(n+1) comparison, no?. Where did the extra n come from?Pseudo-code:procedure last_even_loc(a1,a2,...,an:integers);location = 0;for i = 1 to n    if (a_i = 0) (mod 2) then location = ireturn location;
Why is there a 2n+1 comparison for a linear search algorithm?
algorithms;algorithm analysis;runtime analysis
procedure last_even_loc(a1,a2,...,an:integers)1.location = 0;2.for i = 1 to n3.    if (a_i = 0) (mod 2) then location = i4.return location;statement 1 is executing only once.statemet 2 is executing total n+1 times.statement 3 is executing total n times.statement 4 is executing only once.The running time of the algorithm is the sum of running time of all the statements executed.so running time=1+1+n+(n+1)=O(2n+3)=O(n).so there is total n+1+n=2n+1 comparisons(statement 2 and 3).