1
$\begingroup$

I have a method Func() that has two inner methods Func1() and Func2().

Func1() has a running time of $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))$ and Func2() has a running time of $O(k \lvert K \rvert \lvert V\rvert)$.

What is the running time of Func()?

Is it $\max \{ O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert)),O(k \lvert K \rvert \lvert V\rvert)\} $? or $O(k\lvert M^2 \rvert (\lvert L \rvert +\lvert M \rvert \log \lvert M \rvert))+O(k \lvert K \rvert \lvert V\rvert)$?

If it is the latter one, how can it be simplified?

$\endgroup$
  • $\begingroup$ you have given two complexities for the same Func2(). The question is confusing at the moment. $\endgroup$ – Navjot Singh Nov 3 '18 at 1:37
1
$\begingroup$
  • The summation rule of the big-O notation;

Given $T_1(n) \in \mathcal{O}(f(n))$ and $T_2(n) \in \mathcal{O}(g(n))$, than $$T_1(n)+T_2(n) \in \mathcal{O}(\max(f(n),g(n)).$$

So, if you call $Func1()$ and $Func1()$ inside of your function $Func()$ only once and there is no other significant computation, $Func()$'s running time is;

$$Func() \in \mathcal{O}(\max(k |M^2|(|L|+|M|\log |M|), k | K | | V | )) $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.