Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0 votes
2 answers
30 views

Some questions regarding asymptotic notation of ${n \choose k}$

Is it always the case that ${n \choose k} = O(n^k)$? If it is, then why does the comment from Clement C. in this post state it is only the case when $k$ is a constant? If it is not, then why is the ...
0 votes
2 answers
50 views

Confusion about asymptotic notations in math and computer science

The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science. (...
  • 3
4 votes
1 answer
55 views

Are "almost all" decidable languages not in P?

There's a famous classical circuit complexity result by Shannon that says almost all languages require exponential circuits [[1]], proven by comparing the number of distinct circuits of $n$ variables ...
  • 71
2 votes
0 answers
39 views

Optimal lookup complexity when requiring insertion complexity to be at most $\mathcal O(\log\log n)$?

How can we design a data structure (storing ordered data) that gives the best worst-case lookup complexity possible, under the constraint that we require the worst-case insertion complexity to be at ...
1 vote
1 answer
56 views

Upper bounding this expression

I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$ This ...
1 vote
1 answer
53 views

Proving this recurrence is $n \log n$

I need to prove that $T(n)$ is $\mathcal O(n\log n)$ with the substitution method. $$ T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}_{n/3}T(i).$$ This is my attempt: I assume $T(n) \leq c n \log n$ and ...
1 vote
0 answers
51 views

Runtime of this algorithm

I have an algorithm with running time that satisfies $$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
  • 247
0 votes
3 answers
47 views

Using limits to determine asymptotic bound

By using limits, show that log n! ∈ Θ(n logn). Using Stirling's approximation for n! I get the limit: $$\lim_{n \to ∞} \frac{log({\sqrt{2πn}}*(\frac{n}{e})^n)}{nlogn} = constant > 0$$ When I break ...
0 votes
1 answer
33 views

Understanding why this upper bound is tight

Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree ...
  • 247
0 votes
2 answers
58 views

Asymptotic Relationship between 1/n and 1/2^n

What is the asymptotic relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$? The answer here mentions that both functions are $O(1)$ (because they are always $\leq 1$) but not $\Omega(1)$ (because ...
  • 11
0 votes
0 answers
24 views

Solving a recurrence relation using the Master Theorem

I'm trying to solve this recurrence relation: $T(n) = T(\frac{n}{2}) + T(\frac{n}{5}) + T(\frac{n}{10}) + c_1n$ ; n > 1 $T(n) = c_2n$ ; n = 1 My first thought was to combine the fractions and ...
user avatar
1 vote
0 answers
63 views

Is it true that: $f\notin o(g)$ implies $\exists c>0: f > cg$ infinitely often

My (attempt at a) proof is as follows: $f\in o(g)$ means that $\forall c>0 \exists n_0 \forall n\geq n_0: f(n) \leq cg(n)$. Now taking the complement we get: $\exists c>0 \forall n_0 \exists n\...
  • 11
4 votes
1 answer
89 views

Optimal algorithmic complexity of "a nonrepetitive stack"?

I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'. A ...
  • 1,319
0 votes
0 answers
39 views

Can 0 be a tight upper bound of -4n?

I'm newbie in algorithm time complexity. I had a function, f(n) = 2n2 - 4n. I have to proof that f(n) = O(n2). We can take it ...
0 votes
0 answers
26 views

Proving an asymptotic bound with induction

Suppose we want to prove by induction that $f(n) \in \Theta(g(n))$. How should the induction proof be set up? I'm tempted to say that the base case should prove that $f(1) \in \Theta(g(1))$ and the ...
  • 247
11 votes
3 answers
2k views

Is Big-Theta a more accurate description of worst case run time than Big-O?

Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?" To me, the only difference is that when we say $O(...
0 votes
2 answers
61 views

What is the asymptotic runtime of the below equation?

What is the asymptotic of ${n \choose 3} \log ^4n$ ? I know that ${n \choose 3}$ is in $\cal O (n^3)$, but what about the term $log^4n$ and what about the product of the two?
  • 135
0 votes
0 answers
21 views

Time complexity of Trie autocompletion (multiple variables in time complexity)

I am trying to understand what the time complexity for an autocomplete function for a Trie-based dictionary would be. Every node contains a letter and whether it is the last letter of a word, and if ...
0 votes
0 answers
14 views

How to compare two functions which themselves contain additions/subtraction between two functions?

I'm new to Asymptotic Notation and wanted to know how to compare two functions which contain sub functions or contain addition/subtraction of other functions. For example : f(n) v g(n), where f(n) = a(...
0 votes
2 answers
87 views

Is $n=\Theta(n^{1+o(1)})$?

Is $n=\Theta(n^{1+o(1)})$? To me it appears to be true as $n$ tends to infinity $n^{o(1)} =0$.
  • 35
1 vote
1 answer
56 views

Solve the recurrence $T(n)=T(\frac{n}{2})+\frac{n}{\log n}$ without master theorem

Suppose given the recurrence $$T(n)=T(\frac{n}{2})+\frac{n}{\log n}.$$ I think the answer is $$T(n)=O\left(\frac{n}{\log n}\right).$$ because $$T(n)=T(1)+\sum_{i=0}^{\log n-1} \frac{n}{2^i(\log n-...
-3 votes
1 answer
55 views

Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))

How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?
  • 1
1 vote
0 answers
37 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 ...
  • 11
0 votes
2 answers
43 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 ...
  • 115
0 votes
1 answer
66 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 ...
  • 151
1 vote
1 answer
63 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 ...
  • 43
1 vote
1 answer
39 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 ...
1 vote
0 answers
34 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 ...
0 votes
1 answer
48 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 ...
0 votes
2 answers
57 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 ...
3 votes
2 answers
319 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 $ ...
  • 45
2 votes
2 answers
621 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 ...
0 votes
0 answers
79 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}$ ...
1 vote
4 answers
75 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 ...
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))$
0 votes
0 answers
36 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 ...
3 votes
2 answers
367 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 ...
  • 337
1 vote
1 answer
49 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) ...
1 vote
1 answer
37 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)}$ ...
  • 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 ...
2 votes
1 answer
62 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 ...
  • 187
1 vote
3 answers
53 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 ...
  • 11
3 votes
2 answers
92 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}^{...
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 ...
  • 578
1 vote
0 answers
50 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 ...
  • 578
3 votes
1 answer
87 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 ...
2 votes
1 answer
57 views

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

Say we have this algorithm in Python. ...
  • 133
1 vote
1 answer
45 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: ...
  • 113
1 vote
1 answer
39 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 ...
1 vote
0 answers
79 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 ...

1
2 3 4 5
28