0
$\begingroup$

Is it possible to calculate the complexity of the combined algorithms (TD-TR-SP, TD-SP-TR) provided here:

A new perspective on trajectory compression techniques

In more details, TD-TR-SP algorithm is a combination of TD_TR and TD_SP algorithm. The complexity of TD_TR is $O(n \log n)$ where $n$ is the size of trajectories. The complexity of TD_SP is $O(n^2)$.

Is it possible to obtain the total complexity when combine these algorithms? I am not familiar with Big-$O$ complexities at all.

$\endgroup$
4
  • $\begingroup$ Yes, but it depends on what it means "combining": in principle, if you know how (mathematically speaking) the two algorithms interact, you can (and must) use each complexity estimate in order to derive the new algorithm complexity estimate, no matter if they are expressed by using Landau notation (as it is customary) or not. $\endgroup$ Mar 29, 2020 at 8:56
  • 1
    $\begingroup$ At first the TD_TR is executed and then the TD_SP (in case of TD-TR-SP). Then the result1 from TD_TR and result2 from TD_SP is putting together like "if result1> max_dist_error or result2 > max_speed_error" do; $\endgroup$
    – e7lT2P
    Mar 29, 2020 at 9:33
  • $\begingroup$ Nice! Could you arrange a description of the conditions for the execution and termination of the algorithms in term of the number $n$ of steps already done and put it in the body of your question? This would help other members to understand the problem without having necessarily to access the paper. $\endgroup$ Mar 29, 2020 at 10:04
  • $\begingroup$ Of course, but can you please help me with the complexity? Or you have to see first the description of the algorithms in order to understand? $\endgroup$
    – e7lT2P
    Mar 29, 2020 at 10:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.