Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
4
votes
1answer
596 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
1
vote
1answer
641 views

How to find kth largest element in (max) priority queue in O(m) time?

Here is my exercise. FINDLARGEST(k): return the elements in the heap with key >=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number ...
1
vote
0answers
22 views

Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$ Note: both $n_i$ and $m_i$ are dependent on $n,m$ so they should have ...
3
votes
2answers
61 views

Struggling to understand the symbolism around the big oh formal definition

I'm struggling to understand what exactly T(n), and f(n) is in the above text: When we compute the time complexity T(n) of an ...
0
votes
0answers
15 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
0
votes
1answer
106 views

Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
2
votes
1answer
102 views

runtime of 2 dependent nested for loops [duplicate]

for (i=1; i<=n ;i=i*2){ for (j=1; j<=i ;j++){ basic_step; } } Regarding the above nested loops, I can't seem to understand why is the following ...
0
votes
3answers
67 views

Is there a unit of measurement that can express code execution speed in absolute terms?

I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
1
vote
1answer
42 views

Time complexity of rotation array m times using temporary array

I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the ...
1
vote
1answer
67 views

How to find an algorithm's complexity from actual running times

I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...
1
vote
0answers
138 views

Approaches for analyzing the work, critical path length and parallelism

I'd like to know where to find references and approaches on how to analyze the work, critical path length and parallelism of algorithms. In particular, for solving the type of homework problems below:...
1
vote
1answer
43 views

Proof involving asymptotic complexity

The question in Proof of big-o propositions asked to prove: $O(f(n))=O(g(n))\iff\Omega(f(n))=\Omega(g(n))\iff\Theta(f(n))=\Theta(g(n))$ The accepted answer starts the proof with: Suppose that $...
1
vote
1answer
153 views

Akra-Bazzi method integral diverges

I want to solve this recursion: $$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$ My attempt and issue: None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en....
1
vote
1answer
34 views

Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
1
vote
0answers
30 views

Cuckoo hashing with a stash: how tight are the bounds on the failure probability?

I was reading this very good summary of Cuckoo hashing. It includes a result (page 5) that: A stash of constant sizes reduces the probability of any failure to fall from $\Theta(1/n)$ to $\Theta(...
0
votes
0answers
31 views

Deducing $3^f = o(3^g)$ from $f = o(g)$

I really need help solving the following question: Given: $$f(n) = o(g(n))$$ Prove: $$3^{f(n)} = o(3^{g(n)})$$ My attempt: I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $. I need to ...
1
vote
2answers
178 views

Average case analysis of linear search

Based on CLRS question 2.2: Consider linear search again. How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to ...
3
votes
1answer
59 views

The role of asymptotic notation in $e^x=1+𝑥+Θ(𝑥^2)$?

I'm reading CLRS and there is the following: When x→0, the approximation of $e^x$ by $1+x$ is quite good: $$e^x=1+𝑥+Θ(𝑥^2)$$ I suppose I understand what means this equation from math ...
63
votes
9answers
6k views

Are there any problems that get easier as they increase in size?

This may be a ridiculous question, but is it possible to have a problem that actually gets easier as the inputs grow in size? I doubt any practical problems are like this, but maybe we can invent a ...
2
votes
2answers
96 views

Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (recurrence relation)

We have a function $T: \mathbb{N}\to\mathbb{N}$ defined recurrently: $$T(n)=\begin{cases} 0 &\text{ if } n=0,\\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$ Prove that for ...
2
votes
2answers
54 views

How to use Master Theorem with strange format of $b$ parameter?

I have a funcion $T: \mathbb{N}\to\mathbb{N}$ defined as: $$T(n)=\begin{cases} 6 &\text{ if } n=0,\\ T(n-1) + 6n + 6 &\text{otherwise.} \end{cases}$$ How can I apply the Master Theorem to ...
1
vote
1answer
106 views

Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

I was trying to solve the following question while reviewing master theorem. Which of the following asymptotically grows faster. (a) $ T(n) = 4T(n/2) + 10n $ (b) $ T(n) = 8T(n/3) + 24n^2 $ (c) $ T(...
0
votes
1answer
67 views

What impact does the modulo operator have in a for-loop?

Here's an example of what I mean: ...
3
votes
1answer
14k views

Time complexity of this solution to N-queens problem

I'm trying to figure out the time complexity of this implementation of classic N-queens problem on geeksforgeeks. The goal is to find just one such non-attacking solution(as opposed to finding all of ...
38
votes
4answers
48k views

How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...
5
votes
2answers
819 views

Confusion with analysis of hashing with chaining

I was attending a class on analysis of hash tables implemented using chaining, and the professor said that: In a hash table in which collisions are resolved by chaining, an search (successful or ...
1
vote
1answer
43 views

Comparing different asymptotic notations

Suppose we have 3 algorithms complexity times at the worst case: A = $O(nlogn)$ B = $O(n\sqrt{n})$ C = $\Theta(n)$ In my opinion, it is not possible to define the best solution, since we don't know ...
0
votes
1answer
32 views

Trouble finding what this recurrence solves to [duplicate]

I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$ I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
2
votes
2answers
638 views
2
votes
2answers
2k views

Are “of the order of n” and “Big O” the same thing?

I am learning from the MIT course Introduction to Algorithms. The professor says: Now, remember $\Theta(n)$ is essentially something that says "of the order of $n$". What does "of the order ...
1
vote
2answers
35 views

What does “bounded above” mean in Family of Bachmann–Landau notations?

Per wiki |f| is bounded above by g (up to constant factor) asymptotically with this concrete example, $$f(n) = \log n$$ $$g(n) = n^c = n^{0.000001}$$ Does "bounded above (up to constant factor)...
0
votes
0answers
39 views

how to compute $O(n^{0.000001})$ [duplicate]

this MIT course gives a formula about Big O $$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$ going through wiki, i cannot find a similar Big O properties or usages. how to compute $O(n^{...
1
vote
0answers
48 views

which rule can conduct this formula $\log n = O(n^{0.000001})$? [duplicate]

i am learning this post about Big O, which gives this formula $$\log n = O(n^{0.000001})$$ why is that?
1
vote
2answers
254 views

3 * O(n^2) vs O(n^3)

Currently while I was coding, I got a doubt. While I was solving a particular type of problem I found it to be solved in $O(n^3)$. I have broken that problem and solved it in $O(n^2)$. But to ...
1
vote
1answer
38 views

Asymptotics of a sinusoid

Consider the function $$ f(n) = 2n^2 |\sin(\pi \cdot n/2)|. $$ Which of the following classes does $f(n)$ belong to? $$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$ I'm working in this ...
2
votes
2answers
267 views

Formulating the master theorem with Little-O- and Little-Omega notation

In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this: Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \...
0
votes
0answers
26 views

Calculating the Complexity of a Two Part Algorithm

This is in relation to this post I made. I eventually solved this by the following approach: Take the un-ordered file with all the purchasing data and use the UNIX ...
2
votes
1answer
79 views

Asymptotic analysis with factorial and exponential

I'm solving a complexity question where I have: $$ n!/2^n $$ The goal is to find an upper bound for this. My idea is using the fact that: $$ n! = O(n^n)$$ $$ n!/2^n = O((n/2)^n) = O(n^n)$$ But is ...
2
votes
2answers
566 views

All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$? All the examples that I could think of satisfy the above ...
0
votes
0answers
33 views

Minimization with asymptotic assumption

Given the function $g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}...
2
votes
1answer
25 views

Proving that there exists a distance $d$-dominating set of size $O(n/\delta)$

Let $d > 1$, and consider a graph $G = (V,E)$ on $n$ vertices. A distance $d$-dominating set of $G$ is a set $D \subseteq V$ with the property that for any $v \in V$, either $v \in D$ or $v$ is at ...
0
votes
0answers
36 views

How can I prove the linear time search algorithm takes O(n) time? [duplicate]

The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
2
votes
1answer
128 views

Mathematically calculating time complexity

This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject. Also I ...
7
votes
1answer
433 views

Asymptotics question

Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$? I am really stuck and I tend to believe it's true, but I don't know how to prove it. Any help would be appreciated!
2
votes
3answers
68 views

What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + … + (n-1)2 + n$?

My best guess is that the series $$ \sum_{i=1}^n i(n-(i-1)) $$ becomes $$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$ So the highest term is $n^2$ and ...
2
votes
2answers
618 views

Traveling Salesman Problem: Big O Complexity of Algorithm

I'm trying to figure out how to do this problem in my intro algorithm class, but I'm a little confused. The Traveling Salesman problem (TSP) is famous. Given a list of cities and the distances ...
0
votes
0answers
22 views

Asymptotic Question [duplicate]

Hi how do I find the asymptotic bound for the recurrence T(n) = T(n/2) + T(n/4) + T(n/8) + n? Can I use master theorem or Substitution method only? If so, I need some help for substitution method. My ...
0
votes
3answers
106 views

How can i prove this asymptotic comparison? [duplicate]

This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution: Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$ ...
4
votes
1answer
52 views

Lower bound on $1^k+2^k+\dots+n^k$

I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.) Now I want to find a lower bound on the ...
4
votes
1answer
283 views

Recursion Tree Analysis by Leaves

Assumptions Let's say we have any recurrence relation (however this is perhaps more applicable to "unpredictable" recurrence relations): $$T(n) = \;?$$ For example: $$T(n) = aT\left(\frac{n}{b}\...

1 2 3
4
5
22