Asymptotic of divide-and-conquer type recurrence with non-constant weight repartition between subproblems and lower order fudge terms

While trying to analyse the runtime of an algorithm, I arrive to a recurrence of the following type :

$ $ \begin{cases} T(n) = \Theta(1), & \text{for small enough $ n$ ;}\ T(n) \leq T(a_n n + h(n)) + T((1-a_n)n+h(n)) + f(n), & \text{for larger $ n$ .} \end{cases}$ $ Where:

  • $ a_n$ is unknown and can depend on $ n$ but is bounded by two constants $ 0<c_1\leq a_n \leq c_2 < 1$ .
  • $ h(n)$ is some “fudge term” which is negligeable compared to $ n$ (say $ O(n^\epsilon)$ for $ 0\leq \epsilon < 1$ ).

If $ a_n$ was a constant, then I could use the Akra-Bazzi method to get a result. On the other hand, if the fudge term didn’t exist, then some type of recursion-tree analysis would be straight-forward.

To make things a bit more concrete, here is the recurrence I want to get the asymptotic growth of:

$ $ \begin{cases} T(n) = 1, & \text{for n = 1;}\ T(n) \leq T(a_n n + \sqrt n) + T((1-a_n)n+\sqrt n) + n, & \text{for $ n \geq 2$ } \end{cases}$ $ Where $ \frac{1}{4} \leq a_n \leq \frac{3}{4}$ for all $ n\geq 1$ .

I tried various guesses on upper bounds or transformations. Everything tells me this should work out to $ O(n\log(n))$ and I can argue informaly that it does (although I might be wrong). But I can only prove $ O(n^{1+\epsilon})$ (for any $ \epsilon>0$ ), and this feels like something that some generalization of the Master theorem à la Akra-Bazzi should be able to take care of.

Any suggestions on how to tackle this type of recurrence?

When computing asymptotic time complexity, can a variable dominate over other?

I want to express the asymptotic time complexity for the worst case scenario of sorting a list of $ n$ strings, each string of length $ k$ letters. Using merge-sort, sorting a list of $ n$ elements requires $ O(n\log n)$ . Comparing two strings of length $ k$ has a cost of $ O(k)$ . Therefore, the cost would be $ O(kn\log n)$ .

However, I know some restrictions about $ k$ and $ n$ due to the nature of the problem. In particular, I know that for any list, $ 0 \lt k \leq 20$ , and $ 0 \lt n \leq 80000$ . In other words, the number of words in a list might vary in a much larger range than the length of the words.

In that case, would it be correct to say that $ n$ dominates over $ k$ and therefore the cost could be expressed as $ O(n\log n)$ ? Or does the fact that we are discussing asymptotic costs make those restriction meaningless (as we are describing how the algorithm is impacted by the growth of each variable, regardless of how much they can actually grow)? In general, if two variables are independent, is it possible to dismiss one of them from the asymptotic cost under certain circumstances?

Is the usage for asymptotic notation for these algorithms correct? [duplicate]

So after reading a lot of information around asymptotic analysis of algorithms and the use of Big O / Big Ω and Θ, I’m trying to grasp how to utilise this in the best way when representing algorithms and operations on data structures.

For example there is a recommended website where I got this screenshot from describing Quicksort and I’ve noticed a few issues that stand out to me based on what I’ve learnt.

  1. Is it possible for all notations to represent “Best” “Average” and “Worst” cases? and if so how is this possible? For example for a “Worst” case, How can Big Ω represent the Upper bound. The upper bound is tied to Big O.
  2. I thought in order to find Theta Θ, Big O and Big Ω had to be the same values? In the screenshot “Best” case is n log(n) and Worst case is n^2 so how can Θ(n log(n))?
  3. Take for instance a Hash Table data structure, if you were to perform an analysis on the time complexity for insertion of an element. Would I be correct is saying you could interchangeably say Ω(1) and O(N) or conversely “Average Case is O(1)” and “Worst Case is O(N)”?


Asymptotic Analysis of Nested Loops with Conditionals

I’m trying to run an analysis of a set of nested loops so that I can determine the value of variable sum after the outer loop is finished. The code is as follows:

sum = 0; for (i = 0; i < n; i++) {   for (j = 0; j < i*i; j++) {     if (j % i == 0) {       for (k = 0; k < j; k++) {         sum++       }     }   } } 

Note that this code is in C++. I have no problem doing this sort of analysis via summations for each loop, but the nested ‘if’ conditional is throwing me off. Here’s what I have so far:

  • The 3rd loop is only entered if j is equal to or a multiple of i.
  • The outer and innermost loops have simple bounds that can easily be solved via summation.

Where I get hung up is in regard to defining the lower and upper bounds for the second loop when representing via summation. My current equation is:

$ \sum_{i=0}^{n-1} \sum_{???}^{i*i-1} \sum_{k=0}^{j-1}$

I’m subtracting 1 from the upper bounds since the lower bounds start at 0, not 1.

Does anyone have any advice on how to represent this set of nested loops as summations that I can solve to determine the final value of sum? Any help is greatly appreciated.

Asymptotic analysis for machine learning algorithms

I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity.

I have noticed this is very uncommon. However, I believe it would help us compare these algorithms and decide which one to use for a given scenario.

I am also aware that the running time of most machine learning algorithms is highly dependent on the data. For example, gradient descent algorithm can iterate significantly more times on certain data sets than others.

Considering this, what would be a nice complexity measure for comparing machine learning algorithms?

Proof that quantum entanglement does not increase the asymptotic capacity of classical channel

Consider a classical channel $ N_{X\rightarrow Y}$ which takes every input alphabet $ x\in X$ to output alphabet $ y\in Y$ with probability $ P(y|x)_{Y|X}$ . It is stated in many papers that even if the sender and receiver share entangled quantum states (or even no-signalling resources like a Popescu-Rohrlich box), they cannot increase the asymptotic capacity.

What is the proof of this statement?


A half-answer to this question is in this work, where the authors comment

By itself, prior entanglement between sender and receiver confers no ability to transmit classical information, nor can it increase the capacity of a classical channel above what it would have been without the entanglement. This follows from the fact that local manipulation of one of two entangled subsystems cannot influence the expectation of any local observable of the other subsystem

However, this is a little mysterious to me since it is known (see here) that in other regimes (one shot, zero error, etc.), entanglement between the sender and receiver can be used to boost the capacity of a classical channel. However, all these advantages die away in the case where one uses the channel $ n$ times and $ n\rightarrow\infty$ . Why is this so?

What is the difference between Big(O) and small(o) notations in asymptotic analysis?

What is the difference between Big(O) and small(o) notations in asymptotic analysis? Even though I understand that small(o) is used for a bound that is not tight,is it allowed to use big(O) notaion for a bound that is also not tight e.g can I say that 5n=O(n^3).I am also confused by what this statement in CLSR means “The main difference is that in f(n) =O(g(n)), the bound 0 ≤ f(n) ≤ cg(n) holds for some constant c > 0, but in f(n) = o(g(n)), the bound 0 ≤ f(n) < cg(n) holds for all constants c > 0.” As the value of c will differ in the inequality “0 ≤ f(n)< cg(n) for all n ≥ n0,c>0}. ” for different n0.