Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,319
questions
1
vote
1answer
29 views
Subtraction on Big Theta notation
This is a question I got for an assignment, and I have been stuck on it for the past few days.
Prove that
$\Theta(n)+\Theta(n-1) = \Theta(n)$
Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$
I ...
0
votes
0answers
22 views
Sum of asymptotic notations
Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$?
Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
0
votes
2answers
60 views
Θ, O, Ω, and how they relate to each other as subsets
I'm trying to better understand how Θ(n), O(n), and Ω(n) relate to each other as sets and want to make sure I'm on the right track.
I get that Θ(n) ⊆ O(n) since Θ(n) is stronger and all of its ...
1
vote
1answer
22 views
What would be the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?
What is the correct asymptotic lower bound for $f(n) = 3n^2 + 2n$?
I was thinking that the lower bound would simply be $\omega(n) = cn^2 + n$, for the constant $c = 3$ and integer $n \ge 1$. Indeed, $...
1
vote
1answer
22 views
Asymptotic height of d-ary heap
I know that the height of a $d$-ary heap on $n$ nodes is $\lceil (\log_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's $\Theta(\log_d n)$?
I know the definition of $\Theta, ...
0
votes
1answer
27 views
Sum of a function Θ(g) with a function that is not O(g)
Consider g a function of n: $g(n)$.
Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + ...
0
votes
0answers
43 views
Time complexity of this for-loop
I know, the inner loop here is O(log n). But, I get confused by the multiplication in the outer loop part.
...
-1
votes
1answer
109 views
Why is $n^{1.98}$ an element of $O(n^2)$?
Why is option "(C) $n^{1.98}$ is $O(n^2)$" the question below correct? Is it because "Big $O$" is upper bound meaning worst case, therefore $n^{1.98}$ is not worst case $n^2$ ?
How ...
1
vote
1answer
27 views
Comparing order of growth with n^(logn) - need to know where value comes from?
I'm trying to understand how you compare the following for order of growth.
With the below working out with $f_4$ I don't get where the $x^5$
and $x^6$ come from at the end. With $f_4$ you have $n^{\...
0
votes
2answers
70 views
Is log^2 (n) ∈ O(n) true?
I'm new to algorithm, and I am already overwhelmed with the term ∈ I really could use some good explanation.
1
vote
1answer
30 views
Finding time complexity $T(n) = 2^n T(n/2) + n^n$
I am applying substitution method to find the time complexity of the following recurrence relation. But I am having difficulty solving it past a certain point.
$$T(n) = 2^n T(n/2) + n^n$$
After ...
0
votes
1answer
12 views
Online binary tree creation via $a\to ax$ and $ab\to a(bx)$
I wish to construct a sequence of unlabeled binary trees $T_n$ satisfying the following properties:
$T_n$ has $n$ leaves
$T_n$ is well balanced (height $\lg n+O(1)$)
$T_n$ is obtained from $T_{n-1}$ ...
1
vote
2answers
44 views
Regularity condition for cases 1 & 2
My question concerns the version of the Master Theorem described in CLRS and in this handout.
I already understand the following:
If the regularity condition in case 3 does not hold, then we can't ...
1
vote
1answer
43 views
Why is the time complexity of merge sort with a $\Theta(n^2)$ merge function $\Theta(n^2)$?
The original problem I was solving was what would the time complexity of a merge sort algorithm be, if it used a merge algorithm with complexity $\Theta(n^2)$ instead of $\Theta(n)$. The solution says ...
4
votes
1answer
68 views
Inverse of Ackermann function and $\log^* n$
Consider inverse of Ackermann function, can we conclude that the growth rate of it as the same as growth rate $\log^*n$?
0
votes
1answer
56 views
Quicksort with insertion sort
Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
0
votes
1answer
48 views
Compare growth rate two functions
Suppose $f_1(n)=n\log^*n$,$f_2(n)=n\log h$ that $h$ is number of vertices of convex hull.
Can we conclude that
$$f_1+f_2=O(f_2)?$$
Edited:
Note that, $h$ is a function accroding to $n$ that $h\leq n$, ...
-1
votes
1answer
19 views
How do you get the Bound g(n) of the graph?
We all know that We estimate our running time by drawing a graph and Big O and Big Theta is our worst and average running time respectively and we graph our function like :
$ O(g(n))= f(n)$ and create ...
0
votes
1answer
20 views
Find an integer such that linear equation becomes divisible by another given integer
Given integers a, b, and c all <=n, is there an efficient algorithm to find an integer y
such that a | c + b*y? One brute force approach will be to check for all y = 0 to n
and if there is a ...
0
votes
2answers
39 views
Complexity of calculating sin(nx)
Suppose we are give a natural number $n$, the value of $\sin(x)$ and $\cos(x)$. How efficiently can we compute $\sin(n x)$?
My Thoughts :
The $\sin (n x)$ expansion will have $O(n)$ terms. The power ...
1
vote
1answer
47 views
Arguing that the inverse of Ackermann function is upper bounded by a logarithmic function (i.e. $\alpha(n) = O(\lg n)$)
The text Introduction to Algorithms by Cormen, et. al. defines the Ackermann Function $A$ as follows:
For integers $k \geq 0$ and $j \geq 1$, we define the function $A_k(j)$
$$A_{k}(j) = \begin{cases}...
0
votes
0answers
25 views
Asymptotic Analysis of code that are unusual
We all know that the RUN Time of most of our program are Big O of linear time, quadratic time, cubic time or log time. But Can this be in unusual or uncommon poly time like $x^6-y$ or cosine function ...
1
vote
2answers
39 views
Disambiguating Big-O and Theta for Expressing Time Complexity
Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ?
Can ...
0
votes
1answer
34 views
Give an O(n^2) algorithm to solve
This is my homework question
Given an array A[1..n] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that
A[i] + A[j] = α for a given value α.
Give an O(n^2) ...
1
vote
1answer
40 views
2
votes
3answers
53 views
Number of comparisons for mergesort
In their book An introduction to the Analysis of Algorithms, Flajolet and Sedgewick analyze the number of compares performed by Mergesort along the following lines. They denote by $C_N$ the number of ...
0
votes
1answer
18 views
Proof the recurrence relation of order statistics using induction
I read order statistics from the book The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley
As per the algorithm the recurrence relation given
T(n)<= cn for ...
0
votes
0answers
17 views
Binning a set into subsets deterministically
I have an unordered set of n unique, positive integers. I want to partition it into ceil(n / k) unordered sets of up to ...
1
vote
1answer
37 views
Why doesn't master theorem solve $T(n) = 2T(n/2) + n\lg\lg n$?
Given two recurrences:
$T(n) = 2 T(n/2) + n \lg \lg n$
$T(n) = 4 T(n/2) + n \lg \lg n$
I'd think that both works for master theorem, but the solution is that the first one cannot use masters ...
1
vote
1answer
56 views
What is the Runtime of this recursive algorithm?
I am learning algorithm complexities. So far it has been an interesting ride. There is so much going behind the scenes that I need to understand. I find it difficult to understand complexity in ...
0
votes
0answers
43 views
Suppose f(n) = O(h(n)) and g(n) = O(h(n)). Is f(n) * g(n) = O(h(n) * h(n))?
I understand this should be a relatively easy proof, but I can't seem to understand how to do it.
I know that, by Big O definition:
there exists some value $c_1$ where $f(n) \le c_1 \cdot h(n)$ for ...
1
vote
1answer
34 views
How many functions require precisely $n^2$ gates?
I'm trying to determine an asymptotic bound on the cardinality of the following set of functions. It is the functions with $n$-bit inputs, $\{0,1\}$ output, and requires precisely $n^2$ NAND gates. I'...
1
vote
1answer
48 views
If f(n) = O(g(n)), g(n) = O(h(n)), is h(n) = Ω(f(n)) true?
I have $f(n) = O(g(n))$ and $g(n) = O(h(n))$.
Is $h(n) = \Omega(f(n))$ true, and if so, what constants would make it true?
I was thinking that since $f(n) = O(g(n))$ and $g(n) = O(h(n))$ are true, ...
2
votes
1answer
68 views
$f(O(x))$ vs. $O(f(x))$
I understand what $O(f(x))$ means... $O(f(x))=\{g(x): g(x) ≤ cf(x), c,x_0>0 \}$. But I can't find a clear explanation on the meaning of: $f(O(x)).$ Can you explain the exact definition of this? ...
1
vote
2answers
84 views
Asymptotics of $(6^n-1000)/(2^n+1)$
If $f(n) = 5n^2 + 3n + 7$ can be written as $\Theta(n^2)$, then how to write the following in $\Theta$-notation:
$$ \frac{6^n - 1000}{2^n + 1}. $$
1
vote
2answers
128 views
is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?
is it true that if $f(n)\in O(g(n))$ then $f(h(n)) \in O(g(h(n)))$?
I can't figure out how to prove or disprove this. if it is true, is it true only when the function $h$ is invertible?
6
votes
1answer
170 views
Counting number of swaps to make two strings equal in linear time
The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.
...
5
votes
2answers
160 views
How does $Θ(\log(n!))=Θ(\log(n^n)$?
How does $Θ(\log(n!))=Θ(\log(n^n)$?
I understand why $Θ(\log(n!))=Θ(n\log(n))$ and $Θ(\log(n^n))=Θ(n\log(n))$, therefore $Θ(\log(n!))=Θ(\log(n^n)$. But I am having trouble reconciling this with the ...
1
vote
1answer
61 views
Is $n\log_{2}\log_{2}n = O(n\log_{3}\log_{3}n)$?
I've proven that $n\log_{2}\log_{2}n = \Omega (n\log_{3}\log_{3}n)$ but is $n\log_{2}\log_{2}n = O(n\log_{3}\log_{3}n)$ also true? Looks like it's not and actually $n\log_{2}\log_{2}n = \omega(n\log_{...
0
votes
1answer
38 views
Apparently weaker form of big O notation
If instead of saying there exists some $C \in \mathbb{R}^{+}$ and $N \in \mathbb{N}$ such that for any $n \geq N$ we have $f(n) \leq Cg(n)$ we say that there is some $C \in \mathbb{R}^{+}$ and
some ...
0
votes
2answers
35 views
recurrence with exponentials
I am trying to figure out on how to approach the problem on finding proving the asymptotic of an exponential recurrence. It is described as such:
t(n)=4t(n/2)+2^n with t(1)=1 for n>=5
From what I ...
1
vote
1answer
33 views
Interpreting = in aymptotic notation
We can interpret $f(n) + o(f(n)) = \Theta(f(n))$ as for any $g(n) \in o(f(n))$ there exists some $h(n) \in \Theta(f(n))$ such that $f(n) + g(n) = h(n)$. But can we perceive it as for any $g(n) \in \...
1
vote
1answer
117 views
Meaning of this two-variable asymptotic notation
What does $k \ln(k) = \Theta(n)$ mean? Does it mean that $k$ is a function of $n$ and we actually had better write $k(n)\ln(k(n)) = \Theta(n)$?
0
votes
1answer
44 views
Proving upper/lower bound
$f (n) = Θ(f (n/2))$
The counter example in the solutions was $f(n)=\sqrt{n}$.
But then we get for every $n\ge n_{0}$
$\sqrt{n}\le c_{0}\sqrt{\frac{n}{2}}\ \ ->\ \ n\le c_{0}^{2}\cdot\frac{n}{2}\ \...
2
votes
2answers
68 views
Prove that $f(n)$ is $= \Omega(g(n))$ but not $= O(g(n))$
I am trying to prove the following statement.
if $\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$, then $f(n) = \Omega(g(n))$ but $f(n) \neq O(g(n))$
What I've done so far
Using ...
5
votes
5answers
895 views
Prove a lower bound
Prove: $n^{5}-3n^{4}+\log\left(n^{10}\right)∈\ Ω\left(n^{5}\right)$.
I always get stuck in these types of questions, where there is a $"-(xy^{z})"$ in the expression.
Whenever I see the solutions for ...
1
vote
0answers
85 views
0
votes
0answers
33 views
Which is better $n^3\log n$ or $n^3$ [duplicate]
I am confused between $n^3\log n$ and $n^3$. Normally $n\log n$ is better than $n^3$ but what's about $n^3\log n$
0
votes
2answers
81 views
Having trouble calculating the asymptotic running time of MAX-HEAPIFY
I don't understand the $T(2n / 3)$ part in the recurrence relation for MAX-HEAPIFY in the book CLRS. There is another post that explains it but I can't realize it.
0
votes
1answer
45 views
Need help understanding tightest lower bound ( BigOmega ) of n!
I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
