Information theoretic lower bound under extra information [on hold]Complexity of sorting algorthmsA question...
Gomel chasadim tovim - are there bad chasadim?
Has a sovereign Communist government ever run, and conceded loss, on a fair election?
"If + would" conditional in present perfect tense
Why is there an extra space when I type "ls" on the Desktop?
Why aren't there more Gauls like Obelix?
Can I negotiate a patent idea for a raise, under French law?
Rationale to prefer local variables over instance variables?
Would those living in a "perfect society" not understand satire
Create chunks from an array
Traveling to heavily polluted city, what practical measures can I take to minimize impact?
Smooth vector fields on a surface modulo diffeomorphisms
I can't die. Who am I?
Do Paladin Auras of Differing Oaths Stack?
The (Easy) Road to Code
Professor forcing me to attend a conference, I can't afford even with 50% funding
How do we create new idioms and use them in a novel?
I reported the illegal activity of my boss to his boss. My boss found out. Now I am being punished. What should I do?
How should I solve this integral with changing parameters?
If sound is a longitudinal wave, why can we hear it if our ears aren't aligned with the propagation direction?
What will happen if my luggage gets delayed?
Under what conditions can the right to remain silent be revoked in the USA?
Cycles on the torus
Movie: boy escapes the real world and goes to a fantasy world with big furry trolls
Writing text next to a table
Information theoretic lower bound under extra information [on hold]
Complexity of sorting algorthmsA question about sortingWhich takes more energy: Shuffling a sorted deck or sorting a shuffled one?Lower bound on uncertainty reductionWhat is information theoretic entropy and its physical significance?Bounding mutual information given ROC curve statisticsMutual Information for Gaussian Process (and also Fano's Inequality)Maximum Mutual InformationUnderstanding information entropyRelay channel: Multihop lower bound
$begingroup$
This is a very basic question related to information theoretic lower bound. Suppose I have a sorting algorithm which when asked if a[i] > a[j], also answers another query if a[p] > a[q]. p and q are chosen by the algorithm and guaranteed to not have been answered before. How does this change the information theoretic lower bound of nlogn of sorting algorithms?
information-theory upper-lower-bounds sorting
asked yesterday
Anna FarihaAnna Fariha
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
put on hold as off-topic by Eevee Trainer, Saad, Cesareo, ncmathsadist, Paul Frost yesterday
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, Saad, Cesareo, Paul Frost
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
This is a very basic question related to information theoretic lower bound. Suppose I have a sorting algorithm which when asked if a[i] > a[j], also answers another query if a[p] > a[q]. p and q are chosen by the algorithm and guaranteed to not have been answered before. How does this change the information theoretic lower bound of nlogn of sorting algorithms?
information-theory upper-lower-bounds sorting
asked yesterday
Anna FarihaAnna Fariha
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
put on hold as off-topic by Eevee Trainer, Saad, Cesareo, ncmathsadist, Paul Frost yesterday
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, Saad, Cesareo, Paul Frost
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– José Carlos Santos
yesterday
add a comment |
$begingroup$
This is a very basic question related to information theoretic lower bound. Suppose I have a sorting algorithm which when asked if a[i] > a[j], also answers another query if a[p] > a[q]. p and q are chosen by the algorithm and guaranteed to not have been answered before. How does this change the information theoretic lower bound of nlogn of sorting algorithms?
information-theory upper-lower-bounds sorting
asked yesterday
Anna FarihaAnna Fariha
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
This is a very basic question related to information theoretic lower bound. Suppose I have a sorting algorithm which when asked if a[i] > a[j], also answers another query if a[p] > a[q]. p and q are chosen by the algorithm and guaranteed to not have been answered before. How does this change the information theoretic lower bound of nlogn of sorting algorithms?
information-theory upper-lower-bounds sorting
information-theory upper-lower-bounds sorting
asked yesterday
Anna FarihaAnna Fariha
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Anna FarihaAnna Fariha
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Anna FarihaAnna Fariha
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
Anna FarihaAnna Fariha
1
asked yesterday
Anna FarihaAnna Fariha
1
1
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Anna Fariha is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
put on hold as off-topic by Eevee Trainer, Saad, Cesareo, ncmathsadist, Paul Frost yesterday
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, Saad, Cesareo, Paul Frost
If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as off-topic by Eevee Trainer, Saad, Cesareo, ncmathsadist, Paul Frost yesterday
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, Saad, Cesareo, Paul Frost
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– José Carlos Santos
yesterday
add a comment |
$begingroup$
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– José Carlos Santos
yesterday
$begingroup$
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– José Carlos Santos
yesterday
$begingroup$
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– José Carlos Santos
yesterday
add a comment |
0
active
oldest
votes
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Welcome to MSE. For some basic information about writing mathematics at this site see, e.g., basic help on mathjax notation, mathjax tutorial and quick reference, main meta site math tutorial and equation editing how-to.
$endgroup$
– José Carlos Santos
yesterday