Lower bound on comparison-based sorting

I have a question from one of the exercises in CLRS.

Show that there is no comparison sort whose running time is linear for at least half of the $ n!$ inputs of length $ n$ . What about a fraction of $ 1/n$ of the inputs of length $ n$ ? What about a fraction $ 1/2^n$ ?

I have arrived at the step where for a linear time sorter, there will we $ 2^n$ nodes in the decision tree, which is smaller than the $ n!$ leaves so this is a contradiction but I am unsure of how to formally write out the proof and extend it to the other fractions? The question also states that "for at least half of the $ n!$ inputs of length $ n$ ". I do not quite understand how it affects the number of leaves in the decision tree as any input of length $ n$ will have $ n!$ possible permutations.

Can an algorithm complexity be lower than its tight low bound / higher than its tight high bound?

The worst case time complexity of a given algorithm is $ \theta(n^3logn)$ .
Is it possible that the worst time complexity is $ \Omega(n^2)$ ?
Is it possible that the worst time complexity is $ O(n^4)$ ?
The average time complexity is $ O(n^4)$ ?

IMO it is possible as long as you control the constant $ c$ , but then what’s the point of mentioning any other bound than the tight bounds?

Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $ x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $ x$ ) finding the $ i$ th order statistics can be done in $ O(lg(n))$ time in the worst case. Now in case of an array representing the dynamic set of elements finding the $ i$ th order statistic can be achieved in the $ O(n)$ time in the worst case.[ where $ n$ is the number of elements].

Now I felt like finding a tight upper bound for forming an $ n$ element Red-Black Tree so that I could comment about which alternative is better : "maintain the set elements in an array and perform query in $ O(n)$ time" or "maintaining the elements in a Red-Black Tree (formation of which takes $ O(f(n))$ time say) and then perform query in $ O(lg(n))$ time".


So a very rough analysis is as follows, inserting an element into an $ n$ element Red-Black Tree takes $ O(lg(n))$ time and there are $ n$ elements to insert , so it takes $ O(nlg(n))$ time. Now this analysis is quite loose as when there are only few elements in the Red-Black tree the height is quite less and so is the time to insert in the tree.

I tried to attempt a detailed analysis as follows (but failed however):

Let while trying to insert the $ j=i+1$ th element the height of the tree is atmost $ 2.lg(i+1)+1$ . For an appropriate $ c$ , the total running time,

$ $ T(n)\leq \sum_{j=1}^{n}c.(2.lg(i+1)+1)$ $

$ $ =c.\sum_{i=0}^{n-1}(2.lg(i+1)+1)$ $

$ $ =c.\left[\sum_{i=0}^{n-1}2.lg(i+1)+\sum_{i=0}^{n-1}1\right]$ $

$ $ =2c\sum_{i=0}^{n-1}lg(i+1)+cn\tag1$ $

Now

$ $ \sum_{i=0}^{n-1}lg(i+1)=lg(1)+lg(2)+lg(3)+…+lg(n)=lg(1.2.3….n)\tag2$ $

Now $ $ \prod_{k=1}^{n}k\leq n^n, \text{which is a very loose upper bound}\tag 3$ $

Using $ (3)$ in $ (2)$ and substituting the result in $ (1)$ we have $ T(n)=O(nlg(n))$ which is the same as the rough analysis…

Can I do anything better than $ (3)$ ?


All the nodes referred to are the internal nodes in the Red-Black Tree.

Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. where there was a discussion regarding the fact that finding the minimum of a set of $ n$ (distinct) elements with $ n-1$ comparisons is optimal as we cannot do better than it, which means that we need to show that running time of algorithm which finds the minimum of a set of $ n$ elements is $ \Omega(n)$ .

This is what the text says to justify the lower bound.

We can obtain a lower bound of $ n – 1$ comparisons for the problem of determining the minimum. Think of any algorithm that determines the minimum as a tournament among the elements. Each comparison is a match in the tournament in which the smaller of the two elements wins. Observing that every element except the winner must lose at least one match, we conclude that $ n-1$ comparisons are necessary to determine the minimum.

Now I could make the thing out in my own way as:

TOP-DOWN

What I have done is a top down comparison, but the authors by their words "Observing that every element except the winner must lose at least one match, we conclude that $ n-1$ comparisons are necessary to determine the minimum." seems they are pointing to some bottom up approach which unfortunately I cannot make out.

How,

"That every element except the winner must lose at least one match" $ \implies$ "$ n-1$ comparisons are necessary to determine the minimum".

Theoretical lower bound of finding number of occurrences of a target integer in a sorted array


Given a sorted array of integers and a target integer, let’s say we want to find the number of occurrences of the target integer.

It is well-known that a binary search can give time complexity $ O(\lg n) $ where $ n$ is the size of the array. For example, given an array $ [1,2,3,3,4,5]$ and a target $ 3,$ the algorithm should return $ 2$ since there are two copies of $ 3$ in the array.

Question: Is there a faster algorithms which give time complexity less than $ P(\lg n)?$ Otherwise, is there a proof to prove that $ O(\lg n)$ is the theoretical lower bound?

Finding the upper bound of states in Minimal Deterministic Finite Automata

I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $ L(A_1) \backslash L(A_2) $ , where $ A_1 $ is a Deterministic Finite Automata(DFA) with $ n$ states and $ A_2$ is Non-deterministic Finite Automata(NFA) with $ m$ states.

The way I am trying to solve the problem:

  1. $ L(A_1) \backslash L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2)$ , which is language, that is recognised by automata $ L’$ with $ n*m$ states
  2. Determinization of $ L’$ which has $ (n*m)^2$ states and it is the upper bound of states.

Am I right?

How can an Incubus bound by Planar Binding be prevented from betraying the caster?

Consider Marissa, a 17th level neutrally-aligned Sorcerer with Charisma 20 who knows the Wish spell. A foolhardy incubus, Bob, attempts to seduce her, and Marissa casts Wish to duplicate Planar Binding, cast as an 8th level spell. This casting ignores spell-casting requirements (it happens immediately, not taking 1 hour to cast, and does not consume a 1000gp jewel). The hapless Bob fails his Charisma save, the tables are turned, and he must follow Marissa’s instructions to the best of his ability for the next 180 days. Marissa gives Bob the following instructions:

  1. You must reveal to me any abilities you have that could allow you to circumvent any command given to you by me (you are to reveal each such ability on two separate occasions, but you are not to repeat an ability if you’ve already informed me twice).

  2. You cannot enter the Ethereal plane without me verbally or telepathically saying “Bob, enter Ethereal” within the past 30 seconds.

  3. You cannot polymorph without me verbally or telepathically saying “Bob, polymorph into X” within the past 30 seconds, where X is the name of some small or medium humanoid race. You are only allowed to polymorph into an instance of that race.

  4. You cannot reveal, by any means, that you are subject to this spell (you cannot speak it, write it, broadcast it telepathically, or in any other way indicate that you are affected by the spell, regardless of whether any creature is present).

  5. You cannot induce anyone or anything to cast Dispel Magic on you, or do anything else that would cause this spell to be disrupted (including entering an Antimagic Field).

  6. If you become aware that someone is casting any spell on you, you must immediately inform me (telepathically).

  7. Anytime I am asleep, you are to perform the tasks I’ve assigned to you beforehand. If I do not specify any task on a given day, you are to work on improving yourself in some artisan’s skill.

  8. If any command I give you is ambiguous to you, you must ask me for clarification.

  9. You are to do nothing that will cause me harm.

  10. You are to do nothing that will cause any creature with an Intelligence score (of 1 or more) harm without me giving you a verbal or telepathic command to do so within the past 30 seconds.

  11. The most recent command I give you overrides previous commands, except for the commands I have enumerated here. In particular, if I give a command in the future that countermands any of these commands, you are to ignore that future command and abide by the commands specified here).

For the purposes of this command, harm to a creature involves the Incubus directly (through his own actions) or indirectly (through a lack of action when he could perform an action to stop the harm) causing any of the following:

  • physical or psychological damage (meta-level: a reduction in hit points via any form of damage).

  • any detrimental effect on a creature’s abilities, offense capabilities, defensive capabilities (meta-level: detrimental effects on an ability check, save throw, attack roll, damage roll, or armor class)

  • inducing non-natural aging, sleep, invisibility, obscurement, gaseousness, etherealness, or incorporeality (but if someone wants such an effect, Bob cannot hinder them).

  • levels of exhaustion

  • restrictions/limitations on any form of movement
  • any effect that could cause death or dying
  • detrimental emotional influence (magical or non-magical)
  • mental influence (charms, enchantments, etc.)

Marissa is curious how Bob can manage to circumvent these commands (or otherwise do things to make him problematic to keep around).

Some notes:

  • She has intentionally limited his Ethereal and Polymorph abilities (requiring permission), and put a time-limit on that permission (30 seconds). Without the time limit, the first time Marissa tells him to polymorph, he could argue that he no longer needs to wait for the phrase because it was already uttered.

  • Having someone cast Detect Magic on him is still the biggest risk.

  • Marissa can see various ways that Bob can interpret the “no harm, even through inaction” command in a very literal way that makes him carry people around so they don’t trip and fall (that is within his abilities, after all).

  • Similarly, Bob may need to ask everyone around him so many questions (“Do you really want to fall asleep right now? Did you mean to cast Invisibility on yourself?” etc) to abide by the commands as written that they need to be modified (which may create loopholes…)

  • Even though Bob is only a CR 4 creature, Marissa has many questions about Bob’s mortality and ability to carry a grudge into the future (Bob may have CR 10 or CR 15 or CR 20 “friends”, after all).

What are the ways that Bob can mess with Marissa? What else should Marissa add to her list of commands?