Plz tell me how I would calculate time complexity of the program:

``````for (i=0; i<points.length; i++)
{
if (points[i].lng()<lon && points[j].lng()>=lon ||  points[j].lng()<lon && points[i].lng()>=lon)
{
if (points[i].lat()+(lon-points[i].lng())/(points[j].lng()-points[i].lng())*(points[j].lat()-points[i].lat())<lat)
{
inPoly=!inPoly;
}
}
j=i;
}``````

Edited by Ezzaral: Added code tags. Please use them to format any code that you post.

3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by agugglez

Looks like O(n) from here.

The routine is dependent on points.length. The inner part can be considered constant execution time. As the number of points grow, the amount of time grows in direct 1:1 to them. So O(n).

Edited by Momerath: n/a

Looks like O(n) from here.

The routine is dependent on points.length. The inner part can be considered constant execution time. As the number of points grow, the amount of time grows in direct 1:1 to them. So O(n).

ya it's looking tht it has a complexity of O(n) bt how it is calculated. Can u plz explain it and wht is it's exact complexity.

please explain to us what the algorithm does and wrap the code part in code tags, it's difficult to read.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.