CODEWITHSUNDEEP
algorithmgraphicstime-complexitybig-oraytracing
Loizos Vasileiou
Loizos Vasileiou

Reputation: 704

What is the time complexity here ? O(NlogN) or O(logN^2)?

What is the algorithm appropriate time complexity equation on that case?

A : O(NlogN)

B : O(logN^2)

Where N is the number of Objects (Bounding Volumes) and log the intersections iterations (How many times would a ray bounce).

Set Camera Position (eye position) 

IF (Object – is found in the scene) 
|  Create Bounding Volume (BV)

For (ALL BV)
|  Get Min-Max Values for X,Y Coordinates 
|  Eliminate Intersection Testings 
|  IF (2 or more Objects are close in range)  
|  |  Intersect(Ray, Object(s)) 
|  |  FOR (each Triangle (T) in the object) 
|  |  |  Intersect(Ray, T) 
|  |  |  E.g Detect Colour And Texture
|  ELSE (Do not Intersect)

Upvotes: 0

Views: 651

Answers (1)

Daniel Choi
Daniel Choi

Reputation: 194

The complexity is O(NlogN).

This is because:

1. There's an outer for-loop : With this outer for-loop, your time complexity is already at O(N).

This part may get a little confusing. We are going to consider two cases.

Worst Case: 2 or more objects are close in range every single loop.

This makes the algorithm O(N^2) because now you need to go through the inner for-loop every single iteration!!! However, it is very unlikely that your if statement will always become true... So we need to take care of the best case scenario as well.

Best Case: None of the objects are close in range.

This makes the algorithm O(N) because you do not have to go inside the inner for-loop anymore! We will only check the if statement and move on to our next iteration.

So what is the time complexity? O(N^2) OR O(N)?

Now we talk about amortized run time. Amortized run time simply means considering both the worst case scenario and the best case scenario (More about amortized analysis can be found here: https://en.wikipedia.org/wiki/Amortized_analysis).

So we are considering both O(N^2) and O(N). Assuming that we are running the if statement half of the time (amortized), the time complexity will be O(NlogN).

Is O(NlogN) faster than O(N)? That will only be true if we have more than about a million objects.

Hope this helps!

Upvotes: 3

Related Questions