Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,055
questions
0
votes
0answers
8 views
Question about asymptotic analysis comparing two functions
I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$
Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \...
0
votes
0answers
8 views
The accounting Method analysis for table expansion by tripleling instead of doubling an array
If we double the array every time we get the amortized cost of 3n or 3$ if you prefer.
I was wondering what would it be if we tripled the array size instead of doubling it.
The rational between the ...
1
vote
0answers
31 views
Proving asymptotic bounds
I'm confused if the following approach is mathematically correct
Suppose I have to prove $(\log n)! > n^a$, where $a$ is a constant
I can assume $n = 2^k$
which leads to $k! > c^k$, where $c = ...
-1
votes
1answer
39 views
Solve recurrence with Master Theorem - Polynomially Smaller/Larger
The problem is to solve the recurrence using Master Theorem :
$$T(n) = 2T(n/2)+\log_2 {n}$$
My attempt:
$$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$ I am torn between case 1 & the ...
0
votes
1answer
36 views
Solving a peculiar recurence relation
Given recurrence:
$T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$
The way I solved is like this (using change of variables method, as mentioned in CLRS):
Let $n = 2^k$
$T(...
2
votes
1answer
30 views
minimizing the maximum between a degree of a tree and its height
I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$. i.e. minimizing $\max(k, \log_kn)$ asymptotically.
If I set $k = \frac {\...
1
vote
1answer
29 views
Asymptotic analysis for machine learning algorithms
I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.
I have noticed this is very uncommon. However, I believe it ...
2
votes
1answer
44 views
Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$
I have seen some algorithms with complexities like $\log^3 n$ and $\sqrt n$. In view of getting a better idea on how to compare these I wanted to know for which values of $k$ does $\log^k n \in \Omega(...
1
vote
0answers
19 views
Circuit depth of computing the continued fractions of a rational number
If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input?
I was reading through some notes which ...
0
votes
2answers
55 views
Is the following true? log2(2n) ∈ O(log2(n))?
Is $\log_2(2n) \in O(\log_2(n))$ ?
I don't know how to prove whether this is true or false.
Any help is appreciated
0
votes
0answers
36 views
Binary Search Complexity
I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing ...
-2
votes
2answers
42 views
prove that log((n^2)!)= o(log((n!)^2))
i have a question - how i can prove that:
$\log((n^2)!) =\theta (log((n!)^2))$
i try something like that:
$\log((n^2)!) = 2*(log(n)!)=\theta(2*(log(n)!)=\theta(n\ log(n)) $
$\ \theta(log(n!)^2)=\...
1
vote
1answer
51 views
What is the lower bound for the following equation
f(n) = 32n^2 + 17n + 1.
The lecture slide says that lower bound can be Omega(n^2) or Omega(n).
Some body please guide me why the lower bound can be Omega (n). i know the upper bound which is O(n^2).
...
2
votes
2answers
69 views
Induction proofs in Big-O notation
I'm not sure how go about this question:
Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<...
3
votes
0answers
22 views
Bit complexity of computing the sign of an expression evaluated at an algebraic number
I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
2
votes
1answer
86 views
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (...
2
votes
1answer
50 views
Why is the run time with a loop of this structure considered O(log n)
I used the search function and a good amount of google searches, but wasn't able to get a straight answer on how a loop of the form below, is translated to a proper summation where the function ...
0
votes
0answers
20 views
Quick Clarification Question about Time Complexity in CLRS
I'm reading about the Hiring Problem in "Introduction to Algorithms" and read
Interviewing has a low cost, say $c_i$, whereas hiring is expensive, costing $c_h$. Letting $m$ be the number of ...
1
vote
1answer
48 views
About Big O properties
Suppose I have something like the following:
$f(x) = g(x) + O(x^n)$
And I apply a power $m$ to both sides
$f(x)^m = g(x)^m + \cdots + O(x^n)^m$
My question is whether the following is well ...
1
vote
0answers
35 views
Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate]
How would you go about solving this problem?
I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
2
votes
1answer
68 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 ...
0
votes
0answers
36 views
Summing big-O-notation
prove or disprove
$$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$
I have no idea about where to begin.
what are the theories which should be used here?
0
votes
1answer
30 views
How does $n^c \lg n, 0<c<1$ compare to other common time complexities
Between what two common time complexities would you place $n^c lg n, 0<c<1$?
The following table illustrates the common time complexities.
Source: wikipedia
25
votes
2answers
4k views
Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?
Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
1
vote
1answer
47 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
30 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
38 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
2answers
65 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
188 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
280 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
81 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
41 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
77 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
26 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
61 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
83 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
55 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
34 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
38 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
92 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
69 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
62 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
41 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
15 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
46 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
210 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
42 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$ ...
