# All Questions

206 questions
Filter by
Sorted by
Tagged with
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?
69 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)$?
29 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)$ ...
404 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 ...
49 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. ...
298 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 ...
52 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 ...
28 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$$ ...
102 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
27 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)).
78 views

56 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 ...
59 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 ...
167 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 ...
62 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 ...
106 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 ...
48 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 ...
737 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 ...
75 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)$ ...
423 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.
441 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 ...
299 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 ...
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.
96 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.
58 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.
139 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 ...
117 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, ...
113 views

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

What's the difference between $O(1)$ and $o(1)$ ?
### 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$.