Suppose $f_1(n)=n\log^*n$,$f_2(n)=n\log h$ that $h$ is number of vertices of convex hull.

Can we conclude that $$f_1+f_2=O(f_2)?$$ Edited:

Note that, $h$ is a function accroding to $n$ that $h\leq n$, and according to the input $n$ it can be less than $n$ such as constant.

$n\log h$ is running time of an ouput sensetive algorithm for finding convex hull.

  • $\begingroup$ You need info about $h=h(n)$. Different cases implies different answers. $\endgroup$
    – zkutch
    Oct 30, 2021 at 9:35

1 Answer 1


$h$ is the number of vertices of what convex hull?

If $h$ is a constant, then $f_2 = \mathcal{O}(f_1)$ because $\log^*n\underset{n\rightarrow +\infty}{\longrightarrow}+\infty$.

If I try to interpret more than you wrote, and consider $h$ to be the number of vertices of the convex hull of a set of $n$ points, then you could still have $f_2 = \mathcal{O}(f_1)$, because $h$ could be equal to $3$, even with $n$ arbitrary big.

  • $\begingroup$ Thank you, please review my question, I edit my question. $\endgroup$
    – Ahmad
    Oct 30, 2021 at 9:54

Your Answer

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

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