# Questions tagged [landau-notation]

Questions about asymptotic notations such as Big-O, Omega, etc.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
52 views

### Constant in Complexity of SQRT algorithm

this is my first question in CS so I apologize if this question is off-topic. If we use Newton`s Method for finding square root then complexity is $O(M(n))$ (using Wikipedia Notation: $M(n)$ is the ...
49 views

### Can there be functions in o(1) in algorithm analysis?

I saw a similar question to this one here but it's not quite the same as mine: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$? I've just started a course in data structures and ...
62 views

### Order of growth: substitution of monotonically increasing functions

One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule.  \lim_{n\...
110 views

### If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?

My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but ...
Let f$(n)=O(n)$, $g(n)=\Omega(n)$ and $h(n)=\Theta(n)$. Then $g(n)+f(n)\cdot h(n)$ is equal to what among $O(n)$,$\Omega(n)$ and $\Theta(n)$? Also explain how to evaluate it.
### If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$?
If $f(n)=\Omega(g(n))$ and $h(n)=\theta (g(n))$ then does this implies $f(n).g(n)=\Omega(g(n).h(n))$ I saw a proof where they have proved If $f(n)=O(g(n))$ and $h(n)=\theta (g(n))$ then this implies ...