Questions tagged [landau-notation]

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

249 questions
Filter by
Sorted by
Tagged with
61 views

How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a ...
247 views

Is O((n^2)*log(n)) greater than O(n^(2.5))?

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
67 views

When are log complexities considered equivalent?

Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$? Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.
30 views

Substitution for Landau's O notation formula

I found the following description when I was reading a paper on computational complexity theory. This can be done ... in time 2n･poly(logs,n)+2O(logs)c. For s≤2no(1), the runtime is 2n･poly(n). I ...
48 views

which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]

i am learning this post about Big O, which gives this formula $$\log n = O(n^{0.000001})$$ why is that?
19 views

Run time of pseudo code in big theta notation [duplicate]

I am looking for the run time of the following pseudo code. ...
79 views

How can i prove this asymptotic comparison? [duplicate]

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution: Prove that: $$27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$ ...
88 views

If my algorithm has complexity O(n!*n), can I just write O(n!), or do I have to keep it like O(n!*n)?

Just as I asked in the title: if my algorithm has complexity $O(n!\times n)$, can I just write $O(n!)$, or I have to keep it like $O(n!\times n)$?
32 views

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)$ ...
1k 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 ...
50 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. ...
490 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 ...
54 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 ...
30 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$$ ...
107 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
37 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)).
98 views

58 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 ...
67 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 ...
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 ...
191 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 ...
63 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 ...
107 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 ...
37 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$, ...
52 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 ...
1k 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 ...
83 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)$ ...
500 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 ...
161 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.
524 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 ...
423 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 ...
16 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.
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.