# Questions tagged [landau-notation]

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

264 questions
Filter by
Sorted by
Tagged with
160 views

### Shifted Big Os. How to say O((n+c)!) = O(n!)?

Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is $nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$ Strictly, there is no constant factor that would make ...
48 views

42 views

### Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

I have encountered the following question in my homework assignment in Data Structures course: "Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?" ...
72 views

### Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$? How can the function on the left be compared to a whole set?...
62 views

30 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 ...
43 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 ...
226 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 ...
43 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 ...
140 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 ...
447 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 ...
56 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 ...
82 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?
715 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?
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).$$ ...
53 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}$,...
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\...