Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [landau-notation]

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

-1
votes
0answers
28 views

Does $f(x) \not\in O(g(x))$ imply $f(x) \in \Omega(g(x))$? [duplicate]

Does $f(x) \not\in O(g(x))$ imply $f(x) \in \Omega(g(x))$ for all $f$ and $g$? And does $f(x) \in O(h(x))$ where $h(x)$ is at least $g(x)$ imply $f(x) \in \Omega(g(x))$?
1
vote
1answer
36 views

Asymptotic relation between n! and (n+1)!

I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
1
vote
1answer
37 views

Are the following Big Oh Notations equivalent?

In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent. $\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$ $\...
44
votes
10answers
11k views

O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
0
votes
1answer
66 views

How come O(n) + O(logn) = O(logn)

How come O(n) + O(logn) = O(logn)? When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
0
votes
1answer
45 views

Is this a valid use of big-O notation?

Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results. ...
1
vote
1answer
78 views

Introductory explanation of the Big-Oh properties

I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
1
vote
2answers
47 views

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ? Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
1
vote
1answer
24 views

Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?

We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$. I came up with following proof but i dont know it's correct or not. $$g = O(f)$$ $$g \le c_1*f $$ $$h \le c_2*f $$ ...
1
vote
1answer
80 views

Asymptotic Notation Analysis

2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1 since 2^n may or not be element of O(3^n) I need a hint to figure the problem
0
votes
1answer
23 views

complexity class of functions [duplicate]

What would these statements mean if f(n) and g(n) are functions over natural numbers? g(n) is in Θ(f(n)). and An algorithm is in the complexity class Θ(f(n)).
1
vote
3answers
47 views

What is the constant $C$ in the definition of asymptotic notations?

For example in the definition of $\Theta$: $f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that $$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for ...
0
votes
1answer
28 views

How can I find $\Theta(log(m_1)+…+log(m_k))$ as related to $m$?

given: $$m_1+m_2+...+m_k=m$$ How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$? I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but ...
2
votes
1answer
29 views

Complexity Reduction Analysis

I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the ...
0
votes
2answers
217 views

Two questions about complexity class

Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower? What is the name of the ...
3
votes
1answer
37 views

Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?

Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel ...
0
votes
0answers
70 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
1answer
55 views

Big O understanding given different input sizes

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
1
vote
0answers
45 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
votes
1answer
50 views

Algorithms - In which relation to the big O notation are the functions lg n and ln n? [duplicate]

I want to prove in which relation the two functions stand to each other with the help of a proof. But how?
6
votes
1answer
217 views

What does the “big O complexity” of a function mean?

What do people mean when they refer to the "big O complexity" of a function? What is the big O complexity of $9n^2 + 10n$, for example?
6
votes
3answers
1k views

How did they cancel out O-terms in this fraction?

While reading a book about algorithms, I came across this derivation: $$ \frac{2a_0(2N) \ln(2N) + O(2N)}{2a_0N\ln N+O(N)} = \frac{2\ln(2N) + O(1)}{\ln N+O(1)} = 2 + O\left(\frac{1}{\log N}\right). $$ ...
0
votes
1answer
44 views

Is there a contradiction between “set-theoretic” and “formal” definition of “Big-O”?

$O(n) = \{n, n^{2}, n^{1000000}, 2^{n}, ...\}$ [Source A], [Source B] Say $t_{n} \in O(n)$ By formal definition $t_{n} \leq k \cdot n$ [Source C] But how can this be? Say $t_{n}$ is actually $n^{2}$,...
1
vote
0answers
27 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\...
1
vote
0answers
52 views

how to interpret O(1) + O(2) + … + O(n)? [duplicate]

in the book "Introduction to algorithms"(CLRS) page 49 it says: "The number of anonymous functions in an expression is understood to be equal to the number of times the asymptotic notation ...
1
vote
1answer
49 views

Can the following O(…) expression be simplified?

I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity: $O(kn + k^2L + k^2nL + knL)$ I think I ...
0
votes
1answer
31 views

Asymptotic notation? [duplicate]

can someone pls help How do I prove 2⌊lg n⌋ = Θ(2⌈lg n⌉) 2 ⌈lg n⌉+⌊lg n⌋ = Θ(n2) I'm not too good at maths. I know, lim ( n -> infinty) = f(x)/g(x) if we get a real constant the statement ...
3
votes
2answers
141 views

What does the $O^*$ notation mean?

I'm recently reading some papers on the maximum independent set problem, all the algorithms' time complexity is donated by $O^*()$ notation, like $O^*(1.0836^n)$. One paper says "the $O^*$notation ...
0
votes
2answers
60 views

Question regarding $O(n^2)$ efficiency

I'm going through a video of EDX course which talks about Big O notation. At the end of the video they have some questions but the $O(n^2)$ answer is confusing me. It feels like a mistake, but I just ...
2
votes
2answers
105 views

What $O$ -symbol supresses?

I am reading this book Asymptotic Methods in Analysis by N. G. de Bruijn. It describes the definition of $O$ symbol as A weaker form of suppression of information is given by the Bachmann-Landau ...
1
vote
0answers
32 views

Why base of log is insignificant while considering time complexity? [duplicate]

If so, then $O(log_2 n)$ = $O(log_{10} n)$ = $O(log_e n)$. It is very wired that computer scientist treat them equally. Considering, $(log_2 n)$ = $m$, meaning $n$ = $2^m$ $(log_{10} n)$ = $m$, ...
1
vote
1answer
39 views

Proving asymptotic notations for functions

I recently started learning about asymptotic notations. While I was doing practice questions (not HW) I found various question that stumped me totally. So I just want some pointers on how to go by ...
1
vote
2answers
164 views

Why is $3^{\log_2 n}$ the same as $n^{\log_2 3}$? [closed]

I am reading about divide and conquer algorithm at following link on page on 57 in this link. The document analyzes the running time of the algorithm. At the very top level, when $k = 0$, this works ...
0
votes
1answer
64 views

Theta Manipulation to show $N = \Theta(n/\log N)=\Theta(n/\log n)$

I am studying different models of computation and how algorithms can be interpreted under different models. Here is a math(?) question that has been bugging me. Suppose we have $n = \Theta(N\log N)$ ...
0
votes
1answer
247 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 ...
5
votes
1answer
146 views

When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$?

Also, are they equivalent or are they different? Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.
2
votes
3answers
305 views

Can I use Θ if tightest lower and upper bound are not the same?

When analyzing the asymptotic running time of an algorithm where the tightest lower bound and upper bound are not the same, is it bad to denote the running time in theta notation? If an algorithm has ...
0
votes
1answer
168 views

f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?

All functions are from naturals to naturals. Let f(n) and g(n) be monotonically increasing functions. prove or disprove h(n) = max(f(n),g(n)) => h = O(f) or h = O(g) I've found close questions ...
2
votes
0answers
14 views

Complexity calculus: O(log(n-1) * log(n)) = O(log(n))? [duplicate]

I have a question about calculating the complexity. If i need to do log(n-1) times O(log(n)), will this give me a complexity of O(log(n))? My intuition says yes however I am not sure.
2
votes
2answers
94 views

What does it mean to add up O-terms with different variables? [duplicate]

Is this true? O(n) + O(k) =O(n+k).I have searched for it ,the answers were quite ambiguous and I couldn't find a good explanation.
0
votes
1answer
55 views

is this time complexity subexponential? [duplicate]

Is next time complexity sub-exponential? $O(2^{N^{LOG2(1.5)}}/8)$ unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.
0
votes
1answer
81 views

Prove or disprove the given equivalence [duplicate]

f(n) = n/100 = Ω(n) . I am new at proving asymptotic notations , especially at big-Ω. That's why I even didnt start the beginning myself. I tried to prove myself as looking at other proofs and ...
1
vote
2answers
115 views

What kind of growth is $O(0.24\cdot K\cdot 2^w)$

I've calculated the running time of an algorithm I'm interested in to be $$O(0.24\cdot K\cdot 2^{w})\,,$$ where $K$ and $w$ are both variables. ($K$ is the number of elements in some set, ...
1
vote
1answer
102 views

What's the difference between $O(1)$ and $o(1)$?

What's the difference between $O(1)$ and $o(1)$ ?
2
votes
1answer
48 views

Which is better wording: x grows with $N^2$ or x grows with $O(N^2)$

Which of the following sounds better (or more rigorously): x grows with $N^2$ or x grows with $O(N^2)$ or x grows quadratically with $N$.
1
vote
1answer
90 views

Big O - Equivalence: “Standard” definition vs Limit definition

This question is related to: Landau Notation, Definitions: Limits vs. Cormen's. Consider functions $f, \ g : N \rightarrow R^{\geq0}$. For small-$o$, the definition: $$f(n)\in o(g(n)) \iff \forall ...
2
votes
1answer
249 views

Does the transitivity of big-O notation hold for asymptotically nonnegative functions?

I'm reading the book Introduction to Algorithms and in Chapter 3 it is said that if $f(n)$ and $g(n)$ are asymptotically positive then $$ f(n) = O(g(n)) \text{ and } g(n) = O(h(n)) \text{ implies } f(...
5
votes
1answer
162 views

What does $n^{O(1)}$ mean?

I read an example that said explain what "$f(n)$ is $n^{O(1)}$" means. I can't interpret the $n^{O(1)}$ syntax. I know what Big $O$ notation is, its just that this example looks odd to me.
1
vote
2answers
169 views

Disproving using the definition of O

Formally show that $0.1n + 10\sqrt{n}$ is not $O(\sqrt{n})$ using the definition of $O$ only. I cannot find much on how to solve a problem like this, nor do i know how. Am I supposed to show some ...
3
votes
1answer
263 views

$O(n+nm) = O(nm) = O(m+nm)$?

I am thinking about the worst-case space complexity of an algorithm. Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true? $O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)...