Search code examples
algorithmtheorygraph-theorycomputation-theory

What does this statement about algorithms mean?

"The cost of the algorithm X is linear in the area of the largest used ellipse?"

Does this mean that the cost of algorithms X grows linearly as the area of the ellipse is increased?

Note, that the area of the ellipse is increased by doubling, which means exponentially, right?

Solution

  • If A is the area the algorithm will be O(A).

    If you consider (x/a)^2+(y/b)^2=1 then your algo will be O(a*b)

    If you double the ellipse area at each iteration of your algorithm you'll have a quadratic growth of the area but the total complexity will be O(An) where An is the area during last iteration

    EDIT

    I'll go a little in depth:

    Your algo will do f=A0+A1+...+An operations where Ai is the Area at the i-th iteration we can rewrite the formulation in as f=A0+2*A0+4*A0+...+2^n*A0

    O(f) = O(2^n*A0) where 2^n*A0 = An

    Take a look also at https://en.wikipedia.org/wiki/Big_O_notation