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
2
votes
0answers
51 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 ...
1
vote
0answers
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 ...
1
vote
0answers
39 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\...
0
votes
0answers
93 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 ...
0
votes
0answers
38 views

Assymptotic notation equalities

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.
0
votes
1answer
403 views

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 ...