Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,032
questions
1
vote
1answer
33 views
Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?
I am having difficulties in understanding why the recurrence
$$T(n)=3T(n/4) + n\log n$$
is solvable with Master Method but
$$T(n)=2T(n/2) + n\log n$$
isn't?
Despite they both look very similar ...
0
votes
1answer
26 views
Big-O notation for the given function whose runtime complexity grows faster than the input
I struggle to determine the runtime complexity of a function I thought of while trying to solve this quiz. The quiz itself goes like this:
Write a program to find the n-th ugly number. Ugly numbers ...
1
vote
2answers
31 views
Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$
How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?
0
votes
1answer
24 views
In Big-O notation, what does it mean for T(n) to be upper bounded by something
I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? ...
7
votes
5answers
162 views
Is $n^{1/\log \log n} = O(1)$?
Is $n^{1/\log \log n} = O(1)$ ?
Suppose that $n^{1/\log \log n} = c$ where $c$ is constant.
Taking logs of both sides,
$$\frac{1}{\log \log n}\log n = \log c.$$
I am not able to spot an error. ...
12
votes
3answers
217 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})$?
2
votes
1answer
65 views
Quickly obtaining sums of sets of numbers
We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
1
vote
2answers
36 views
Summation of asymptotic notation
How can we solve summation of asymptotic notations like given below:
$$
\sum_{k=1}^{n-1} O(n).
$$
4
votes
1answer
76 views
Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$
I am trying to understand the asymptotics of
\begin{equation}
f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})}
\end{equation}
In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
1
vote
1answer
23 views
The space complexity of a function that allocates space based on the input value and not size
What is the space complexity of the following hyphotetical function:
void function(int n) {
int[] array = new int[n]; // allocate array of size n
return;
}
...
2
votes
2answers
55 views
How to determine time complexity with a simple way?
I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−...
-2
votes
2answers
73 views
Show that: $0.01n \log n - 2000n+6 = O(n \log n)$
Show that $0.01n \log n - 2000n+6 = O(n \log n)$.
Starting from the definition:
$O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
2
votes
1answer
54 views
Show that the union of Θ and o is not O
Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$
I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would ...
2
votes
0answers
32 views
Difference Between $n^{\Omega{(1)}}$ and $\Omega{(n)}$ [closed]
I am not sure about the difference between $n^{\Omega(1)}$ and $\Omega(n)$. It seems to me that the only difference is that $n^{\Omega(1)}$ can contain some sublinear functions, i.e., $n^{\frac{1}{2}}$...
2
votes
1answer
45 views
Big theta of function with multiple types of n [duplicate]
I have the following function:
$\displaystyle\frac{n \cdot 7^n+\frac{8}{n!}}{(n+7) \cdot 7^n}=\Theta(1)$
I don't how they come to this. What is the proper way to analyse a function to theta notation?...
1
vote
1answer
36 views
Is log(n) equivalent to (log(n))^x for big-O analysis?
My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.
ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$
From the ...
4
votes
1answer
73 views
Solving $T(n) = 2T(n/2) + T(n-1)/\log n$
I am interesting in the asymptotic rate of growth of the following recursion:
$$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$
with base case $T(1) = 1$.
I'm having trouble of solving this recurrence ...
2
votes
1answer
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.
1
vote
3answers
58 views
How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?
following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity.
I tried to derive it on paper.
Let T(n) =...
2
votes
1answer
27 views
Splitting summations?
From CLRS Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,
...
1
vote
1answer
54 views
Is $(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$?
I would like to express $(\sqrt{n})!$ in terms of $Θ()$ notation.
My approach is the following:
$$(\sqrt{n})!=f(n)\Leftrightarrow$$
$$\log(\sqrt{n})!=\log(f(n))$$
Now from Stirling's approximation ...
0
votes
1answer
46 views
Simplifying this expression with big O when several variables are involved
I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows :
\begin{...
0
votes
0answers
13 views
Detailed explanation of Perlin Noise algorithmic complexity
I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array ...
2
votes
1answer
43 views
Showing that $n\log n - n$ is $\Omega(n)$
Prove that $n\log{n} − n$ is $\Omega(n)$.
I do know the answer:
$\log{n} ≥ 2, \forall n \ge 4$.
Thus, $n\log{n}−n\ge n ,\forall n\ge 4 \implies n \log n − n ∈ Ω(n)$.
But can someone please ...
4
votes
2answers
194 views
Is asymptotic ordering preserved when taking log of both functions?
In one of my exercise sheets I have the following question;
Let $f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove; $\ln(f(n)) \in O(\ln(...
1
vote
1answer
35 views
What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]
What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ ...
1
vote
1answer
50 views
Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?
From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
2
votes
1answer
46 views
Spotting the difference between two arrays using divide-and-conquer
Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index.
For ...
2
votes
0answers
38 views
Why can't we use the Master Theorem on recurrences with floor or ceiling operations? [duplicate]
From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$...
2
votes
1answer
37 views
Can we apply the Master Theorem to the following recurrence?
Our recurrence is
$$
T(n)=
\begin{cases}
T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\
1 & \text{if $n=1.$}
\end{cases}
$$
I have identified $a = 1 > 0$, and $b = 2 > 1$...
3
votes
2answers
43 views
How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$
In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition
\begin{align*}
\...
0
votes
1answer
41 views
Bubble sort: how to calculate amount of comparisons and swaps
For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do ...
2
votes
1answer
41 views
Solving a recurrence relation involving square roots
Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n. $$
How can I solve this recurrence relation, which involves square roots?
0
votes
1answer
36 views
Find function that satisfy the relation
Can you find the function that satisfy the relation?
$$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
3
votes
1answer
26 views
Prove or disprove that $log^{k}(n) \in O(\sqrt{n}) \forall k > 0$
I'm trying to solve the problem described in the title. By using the free version of wolfram and testing some increasing values of $k$ I get that:
$$\lim_{n \rightarrow \infty} \frac{log^{k}(n)}{\...
0
votes
0answers
12 views
Growth of n/logn vs n^(1+e) [duplicate]
Is $\Theta(\frac{n}{log(n)})$ faster growing function than $\Theta(n^{1+\epsilon})$, where $\epsilon > 0$?
0
votes
1answer
40 views
Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$
I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that?
Algorithm A
...
2
votes
3answers
94 views
How can $\Theta$ and $O$ complexities be different?
From the definition of the $\Theta$-notation,
$$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$
We can see that the ...
5
votes
2answers
93 views
What constant in the latest fast matrix multiplication is hidden by Big-O notation?
I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has ...
3
votes
0answers
48 views
Does a function that belongs to θ(n) belong to O(n^2)? [closed]
My understanding is that the answer is yes. To be θ(n) implies O(n), which itself implies O(n^2).
In other words, a function that is tightly bounded by n is trivially upper-bounded by n^2 as well.
...
-1
votes
1answer
42 views
confused with Time Complexity [duplicate]
I was reading book related to Time Complexity, and came up with 4 lines of equations that I could not understand properly, could you please explain why are those true?
1) $n = o(n\log\log n)$
2) $...
1
vote
1answer
66 views
Running time of algorithm (effect of j*j in for loops) - Theta Runtime
In Theta notation what are the running times of these algorithms?
Algorithm 1
for i=1..n
j=1
while j*j <= i:
j = j + 1
Since the outer loop ...
2
votes
0answers
38 views
Asymtotic bound for recurrence of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution
What can be an initial guess for finding the tight asymptotic bounds of $T(n)=2T(n/2)+ \sum_{i=0}^{n} (i+2)^2$ using substitution method?
0
votes
2answers
96 views
Runtime complexity of a brute force factoring algorithm? (in terms of bits)
Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
2
votes
1answer
26 views
Proving that $S_1+S_2 \leq f^{-\omega(1)}$
I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $ . For a particular $S_1,S_2,f$. Does it suffice to prove there ...
0
votes
0answers
23 views
Time complexity of simple function related to bits
I am wondering about correct answer to this task from a yesterday's test:
A function Pow which calculates $y = a^k$ is given, where $k$ is an
integer of length ...
0
votes
1answer
72 views
How to justify $f(n) = O(g(n))$ [duplicate]
The following question is in my homework:
Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$?
I understand how $f(n)$ is the upper bound of $g(n)$. ...
0
votes
0answers
23 views
Asymptotics and logarithms/exponents
We have four categories:
additive constants, multiplicative constants, polynomials, and
exponentials
When determining the growth order of functions, we only care about polynomials and ...
4
votes
1answer
72 views
Exact meaning of $2^{\mathcal{O}(f(n))}$
In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time.
For example he says that the running time of a single-tape ...
2
votes
1answer
19 views
Asymptotic Relationship from Limit
F(n) = n-100
G(n) = n-200
I am trying to show the asymptotic relationship between these two functions using limits.
I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c.
...
