Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
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

Recursion analysis using Master Theorem

I have the following algorithm: ...
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(...

1
2 3 4 5
27