# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,114 questions
Filter by
Sorted by
Tagged with
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:...
44 views

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 ...
31 views

69 views

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

Here's an example of what I mean: ...
361 views

### Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
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.
674 views

### Bubble Sort with “while” loop - why is average case n^2?

If Bubble Sort is written as: ...
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)...
40 views

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 ...
80 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 ...
576 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 ...
33 views