Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
1 vote
0 answers
26 views

Algorithms with different upper and lower bounds

I am preparing a list of algorithms for which big theta expression for (worst case) runtime is not known. This is for a class to demonstrate the point that tight analysis of an algorithm may not be ...
user avatar
  • 11
0 votes
2 answers
41 views

If $f \in \mathcal{o}(g)$, does $f \circ g \in \mathcal{o}(g \circ f)$?

It's a widely known fact that $\lambda n. \left\lfloor \lg n! \right\rfloor \in \mathcal{O}(\lambda n. \left\lfloor \lg n \right\rfloor!)$. Is it also true (I tried and haven't found a counterexample ...
user avatar
  • 115
0 votes
1 answer
65 views

Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?

Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m*O(\log N)$ or ...
user avatar
  • 151
1 vote
1 answer
49 views

Difference between "almost-linear" and "quasilinear" time complexities

In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$. This is similar to the notion ...
user avatar
  • 43
1 vote
1 answer
35 views

Contradicting asymptotic analysis in recurrence equation?

I'm trying to solve the recurrence equation from CLRS ed 2. $$ T(n) = 2T(\sqrt{n}) + 1 $$ The question says the solution should be asymptotically tight, but at first I didn't read it and solved it ...
user avatar
1 vote
0 answers
27 views

Does creating an array count as a primitive operation under the RAM model?

int[] arr = new int[10]; Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
user avatar
0 votes
1 answer
39 views

Solve Recurrence T(n) = 4T(n/4) + n*[log(n)]^2

I am trying to solve T(n) = 4*T(n/4) + n*[log(n)]^2 I decided to use Master Theorem so I found a,b=4 and logb(a)=1. I thought that 3rd case is the solution but I ...
user avatar
0 votes
2 answers
49 views

A little confusion with Big Theta time complexity

I came across one Big Theta expression: Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way. As per definition of Big Theta.. any function ...
user avatar
3 votes
2 answers
305 views

Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails

Given the algorithm MYSTERY-ALG(n >= 0) 1 if n < 3 then 2 return 1 3 else 4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1) I defined a recurrence $ ...
user avatar
  • 45
2 votes
2 answers
615 views

An α-good tree with n nodes has height O(log n)

Let $α \in [0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by $|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We ...
user avatar
0 votes
0 answers
66 views

Worst case lower bound of the general number guessing problem

I have the following problem: Let Alice and Bob be two people playing games. Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
user avatar
1 vote
4 answers
72 views

Why is $a^{\log_b n}$ the same as $n^{\log_b a}$?

I was watching video Lec 2 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005, where professor Erik Demaine said that $a^{\log_b n}$ is the same as $n^{\log_b a}$. Can someone ...
user avatar
0 votes
1 answer
52 views

equivalency of some facts in $O$ notation

I misunderstanding about some logarithm property in algorithm course: is it correct that we say following three term is equivalent? $O(\log a + \log b)$ $O(\log (ab))$ $O(\log (a+b))$
user avatar
0 votes
0 answers
28 views

The total number of nodes and the height of a ternary search tree

So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
user avatar
3 votes
2 answers
316 views

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

Given the recurrence $$T(n) = 2T\bigg(\frac{n}{8}\bigg) + 2T\bigg(\frac{n}{4}\bigg) + n$$ My professor says that $T(n)$ is $O(n\log n)$ but I have calculated a complexity of $O(n)$ as shown below with ...
user avatar
  • 337
1 vote
1 answer
48 views

Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence: $$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$ Later, they write the same recurrence as $$T(n) ...
user avatar
1 vote
1 answer
32 views

Comparing two functions rate of growth

This is pretty simple and I THINK I know the answer to the question, but I don't know how to prove it formally. Below follows the question. Question. Compare the functions $f(n) = \frac{n^2}{\log(n)}$ ...
user avatar
  • 187
-2 votes
2 answers
57 views

Prove $n\log n\neq O(g(n))$ where $g(n)$ alternates between $\log^*n$ and $n!$

I have to prove that $f(n) \neq O(g(n))$, where $f(n) = n\log n$ and $g(n)$ is $\log^*n$ if $n$ is odd and $n!$ if even. So my thought is to say that $f(n) = O(g(n))$ and then with the definition ...
user avatar
2 votes
1 answer
58 views

Trying to understand the basic about recurrence trees

I have little background on recurrence trees, and I am working on the following exercise: Exercise. Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we ...
user avatar
  • 187
1 vote
3 answers
48 views

A function which is both $o(\log^* n)$ and $\omega(1)$

I've been trying to find a function $T(n)$ whose asymptotic rate of growth satisfies both of the following conditions: $T(n)= o(\log^*n)$ $T(n)= \omega(1)$ But I can't think of a function with this ...
user avatar
  • 11
3 votes
2 answers
68 views

Linearity property of summation applied to Big Theta notation (CLRS math background appendix)

Section A.1 of the Mathematical Appendix of the CLRS, the third edition, page 1146, contains the following formula stating linearity property of summation applied to $\Theta$ notation: $$ \sum_{k=1}^{...
user avatar
0 votes
1 answer
22 views

How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$?

Section 4.4 of Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein gives the following to verify that $O(n^2)$ is an upper bound for ...
user avatar
  • 576
1 vote
0 answers
39 views

Given T(1)=1 and $T(n) = 3T(n/4) + cn^2$, does it make sense to yield $T(2)=T(1)+c2^2$?

Section 4.4 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" illustrates how a recursion tree provides a good guess ...
user avatar
  • 576
3 votes
1 answer
75 views

Find the flaw in the 3SAT solver algorithm

I consider decision version of 3SAT problem. Main idea is to find congruent clauses and construct such maximum formula, which satisfiability/truth table won't be changed. In case of unsatisfiable ...
user avatar
2 votes
1 answer
55 views

Which approach of mine for an algorithm upper bound is correct?

Say we have this algorithm in Python. ...
user avatar
  • 133
1 vote
1 answer
42 views

Newbie needs some explanation on the following code and O-expressed time complexity

I am learning data structures and algorithms currently, and want to understand how the following codes received their O-notations. Code example #1: ...
user avatar
  • 113
1 vote
1 answer
37 views

Find the proper hypothesis for the substitution method for a recurrence problem

I'm trying to solve a recurrence problem using substitution method: Given the following recurrence equation: $ T(n) = \begin{cases} 3 &n = 0 \\ 3T(\frac{n}{5}) + T(\frac{n}{6}) + n&n ...
user avatar
1 vote
0 answers
77 views

Recursive algorithm running time?

I would like your opinion on how to detect the T(n) (Running Time) for the following recursive algorithm. Charm is an algorithm for discovering frequent closed itemsets in a transaction database. A ...
user avatar
-1 votes
2 answers
85 views

Which is larger: $n^{3/2}$ or $n^{\log n}$?

We know that $f(n)$ is $\mathcal O(g(n))$ if $\exists c\ge0$ s.t. $$\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = c.$$ Let $f(n)=n^{3/2}$ and $g(n)=n^{\log n}.$ When I am applying L'Hôpital's rule for $$\...
user avatar
  • 1
1 vote
1 answer
37 views

In the theta notation definition, is it possible that $n_0$ could equal 0?

This is the definition of theta notation: The function $T(N)$ is $\Theta(g(N))$ if there exist positive constants $C_1$, $C_2$ and $N_0$ such that $C_1g(N) \le T(N) \le C_2g(N)$ for all $N \ge N_0$. ...
user avatar
  • 185
1 vote
1 answer
36 views

Tight analysis on a custom data structures with Insert and Remove-Min

I have a data structure supporting the operations Insert(X) and Remove-Min(). Remove-Min() ...
user avatar
  • 149
0 votes
0 answers
40 views

Proving transitivity of big-omega and big-theta notations

I am trying to understand mathematical proofs and their applications to big-omega $\Omega$ and big-theta $\Theta$ notations. The first one is transitivity: $f \in O(g) \; and \; g \in O(h) \Rightarrow ...
user avatar
  • 1
1 vote
1 answer
92 views

Time complexity of an algorithm in the $\Theta$ notation

Consider the following algorithm: res := 0 for i := 1 to n do j := i while j mod 2 = 0 do j := j / 2 res := res + j What's its time complexity ...
user avatar
  • 13
4 votes
1 answer
380 views

Big O vs. Big Theta for AVL tree operations

On the Wikipedia page for AVL trees, the time/space complexity for common operations is stated both for average case (in Big Theta) and worst case (in Big O) scenarios. I understand both Big O and Big ...
user avatar
0 votes
1 answer
47 views

Do tasks that take up more memory/space always take more time?

Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep ...
user avatar
-3 votes
1 answer
55 views

Solve the recurrence $3T(n) = T(n/3)+ \sqrt{\log n}$

How can you solve the recurrence $$3T(n) = T(n/3)+ \sqrt{\log n}$$ using the master theorem? I am lost in this question.
user avatar
1 vote
1 answer
84 views

Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$ is $O(n\log_2\log_2n)$, where $T(1) = Θ(1)$. I tried to form the Induction Hypothesis but didn't succeed in choosing the right one. Try 1: If we ...
user avatar
  • 45
1 vote
1 answer
27 views

How can we assume the asymptotic complexity of 1/2n^2 - 3n

I am trying to understand how asymptotic complexity of the given function is calculated based out of Introduction to algorithms by Thomas Cormen. In the book we are trying to solve inequality for $f(n)...
user avatar
3 votes
1 answer
105 views

Analytic combinatorics and less-precise running times

Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
user avatar
  • 315
5 votes
3 answers
146 views

Asymptotic of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$

I'm trying to figure out the asymptotic estimate of $\frac{(\sqrt{n}+n-1)!}{(\sqrt{n})!(n-1)!}$. I think it is $\omega(2^{\sqrt{n}})$ and am trying to prove it by showing $\lim_{n \rightarrow \infty} \...
user avatar
  • 53
0 votes
0 answers
28 views

Why are we allowed to ignore constant factors of $g(x)$ in recurrence while they are important in solving the recurrence?

I'm trying to learn about asymptotic notations and recurrences and I use MIT 6.042 Mathematics for Computer Science as my resource. and I have some questions about the Professor's talks. He said: ...
user avatar
  • 1
1 vote
3 answers
51 views

Will Big Theta not apply when $f(n)$ and $g(n)$ are of different order?

I'm currently taking my algorithms class, and I learnt that Big theta is defined as follows: $f(n) = \Theta(g(n))$ if there exist constants $c_1, c_2, n_0 > 0$ such that $0 ≤ c_1g(n) ≤ f(n) ≤ c_2g(...
user avatar
  • 21
1 vote
2 answers
96 views

Solve the recurrence equation $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$

I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way: $n = 2^k$ $2^{\frac{2}{k}}\cdot T\left(2^k\right)+\...
user avatar
0 votes
2 answers
90 views

n! and 2^(n^2); which one grows faster

I can't figure this out; is $2^{n^2}=O(n!)$ or is it the other way around? Any help is appreciated!
user avatar
1 vote
1 answer
93 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 ...
user avatar
0 votes
0 answers
27 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 ...
user avatar
  • 13
1 vote
3 answers
127 views

Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
user avatar
1 vote
1 answer
53 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, $...
user avatar
2 votes
1 answer
94 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, ...
user avatar
0 votes
1 answer
29 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) + ...
user avatar
  • 13

1
2 3 4 5
28