https://en.wikipedia.org/wiki/Midpoint_circle_algorithm
https://www.geeksforgeeks.org/mid-point-circle-drawing-algorithm/
I have been looking into the midpoint circle algorithm and have come across conflicting information on its time complexity. On the Wikipedia page, complexity is not mentioned, but in the GeeksforGeeks article, it is listed as O(x – y).
In the above geeksforgeeks article it mentioned
Time Complexity: O(x – y)
Auxiliary Space: O(1)
As x and y is always unchange and it is a number, should the time complexity be O(1) or O(r) where r is the radius of the circle?
I guess O(r) as loop through a 2d vector with n * m size is O(N*M)
If I want to loop through the circumference of circle it should be O(2 * pi * r) where constant can be take away and become O(r)
If I want to change a bit of the algorithm and loop through every cell inside the circle it should be O(r^2) , which come from O(pi * r * r) and take away the constant pi?
Disclaimer : Did not take any algorithm course in Uni , trying to self learn CS.
>Solution :
IMO, O(X-Y) is meaningless.
To draw a full circumference, the algorithm sets 4R pixels. Computing the coordinates of the pixels takes constant time (essentially a handful of additions). So O(R) is correct.
To draw a whole disk, you set about πR² pixels. A simple method works by scanning the circumscribed square, comprised of 4R² pixels.