OK lets settle this. You have a lot of numbers in random order. You divide them in half. There are two numbers - the highest and the second highest you are interested in. There are four equally likely possibilities:
1) both numbers are in the first half
2) both numbers are in the second half
3) the high number is in the first and the second highest is in the second half
4) the high number is in the second half and the second highest is in the first half
Since the sum of probabilities is 1 (100%) and each outcome has equal probability, each outcome has a probability of 25%. The specific outcome of interest is scenario 4) which has a probability of 25%. Hope that makes it plain.

It's very doubtful that you have helped him at all. The paper essentially provided this same explanation, but he didn't grasp it because he lacks the fundamental understanding of the first lesson in probability to do so. The worst outcome is actually that he understands the explanation well enough to be satisfied with it, because then he will think that he actually learned something about HOW to solve the problem and he hasn't. The fact that he is unable to recognize that the problems of the tallest person in a group of people in two sets of seats in a stadium, or the solitary green M&M in two jars of M&Ms, or the sole black marble in two bags of marbles is the exact same as the largest number in a set of numbers split randomly into two halves demonstrates this. But now, thinking that he DOES understand the problem because someone spoon fed the solution to him, he can go on his way only to be exactly back where he started on the very next problem he is given.

What he needs to do is focus on gaining the ability to understand and work with the fundamental concepts of whatever the subject his, but he has no desire to put in the effort to do that -- he just wants someone to show him the solution to the problem he has right this moment and doesn't want to actually learn anything about how to solve it.

I'm not clear what the paper is about. Probably sorting algorithms. Some sorting methods assume the numbers to be sorted are truly random, and work pretty well if they are. But if they are in a specific sequence (the adversity, or worst case situation) the sort takes a lot longer. A bubble sort is probably the worst sort algorithm, but a shell sort is a modified bubble sort and normally runs much quicker. But if the input is ordered in a particular way, the shell sort takes as long as a bubble sort.
Bubble sort and shell sort don't need a lot of work space because they sort by swapping elements. If there is plenty of space other algorithms are faster and less easily disrupted by specific ordering of elements (merge sort for instance).

While sorting algorithms are certainly included, the paper is far more general than that. I'm guessing the course (this CS264 mentioned in the title) is probably an Analysis of Algorithms course or something similar. Based on the description in the first part of it, it is one of a series of papers/lectures on process modeling and analysis intended to present a number of different data models, explore what kinds of situations those data models are and are not applicable to, and be able to analyze different expected performance metrics based on those models. This particular set of lectures appears to be focusing on ways of performing an average case analysis of different algorithms, which is often a lot more challenging than doing a worst-case analysis.

 

Actually, the problems we are asking you ARE your original question (or the very first step involved in it), just restated using different words because the words in the original problem are leading you down a rabbit hole.

That's because you clearly don't understand the fundamental concepts required to solve the question. We are trying to help you build those fundamentals so that you identify what is important in the original problem by seeing that it is the exact same problem, from a probability standpoint, as the more obvious and simpler problems we are asking you (and that you refuse to even attempt to answer).

We could walk through the logic on THIS problem in excruciating detail and, at best, you will THINK you understand it. But if you were given an identical problem tomorrow that is simply phrased a bit differently, you'd be right back here asking for someone to spoon feed you a solution to that one, too, because you won't have learned anything about HOW to identify what the problem really is, to put it into terms that you can work with, and to then actually work with that information without someone else showing you step-by-step how to do THAT problem.

<We could walk through the logic on THIS problem in excruciating detail and, at best, you will THINK you understand it. But if you were given an identical problem tomorrow that is simply phrased a bit differently, you'd be right back here asking for someone to spoon feed you a solution to that one >

If you are afraid of this please close down this forum. As long as this forum exists, I would keep asking questions. You can't force me to stop asking questions. Also you have to improve your strategy. You must work in a step-wise manner. If you are seeing that I am not able to answer your question, then you have to provide me a solution or identify my mistakes. If you are not doing this then you are wasting my time and forum resources because Forum database has to store what ever you are telling me in the context of helping me. But actually you are not helping me because you are jumping from question to another question. Thus instead of helping me you are increasing my problems and forcing me to learn something else which is not required urgently. If you want me to learn something else you can show me a link and then you can check my solution and identify where I am wrong instead of firing me or overdosing me with another question.

Zulfi.

 

OK lets settle this. You have a lot of numbers in random order. You divide them in half. There are two numbers - the highest and the second highest you are interested in. There are four equally likely possibilities:
1) both numbers are in the first half
2) both numbers are in the second half
3) the high number is in the first and the second highest is in the second half
4) the high number is in the second half and the second highest is in the first half
Since the sum of probabilities is 1 (100%) and each outcome has equal probability, each outcome has a probability of 25%. The specific outcome of interest is scenario 4) which has a probability of 25%. Hope that makes it plain.
I'm not clear what the paper is about. Probably sorting algorithms. Some sorting methods assume the numbers to be sorted are truly random, and work pretty well if they are. But if they are in a specific sequence (the adversity, or worst case situation) the sort takes a lot longer. A bubble sort is probably the worst sort algorithm, but a shell sort is a modified bubble sort and normally runs much quicker. But if the input is ordered in a particular way, the shell sort takes as long as a bubble sort.
Bubble sort and shell sort don't need a lot of work space because they sort by swapping elements. If there is plenty of space other algorithms are faster and less easily disrupted by specific ordering of elements (merge sort for instance).

Thanks you have proved that it was just a matter of 8 lines. It was not a million dollar question. This would really help me a lot. Now I can progress to in this topic. This problem has completely stuck me. You have opened the path for me to explore that topic further. This is the advantage of forum. We must get relieve when we post on the forum. This is how our cooperation would increase. If we won't do this then we are not taking advantage of this technology. It allows people of different technologies to understand inter-related problems.

I think WBahn must improve. Time and resources are important. He can give only one set of questions. That's fine. I would surely reply. If my reply is wrong, he has to tell me where I am wrong instead. I am not asking him the answer. But he should not come up with another set of questions. This way over focus will change. But what he is doing is that he asks so many questions for small solutions (like 8 lines as you have proved above) that a person can go away from his actual topic and becomes engaged in irrelevant things. I would appreciate his work. His question are of great class and his explanations are wonderful. I learned a lot from him. I think I must accept that a person can't have all the good things and we must accept him wholly and not partially. So I must appreciate and thank him.

 

If you are not doing this then you are wasting my time

Don't fret, I won't waste your time any more.

 

Hi,
Yes, I am not stopping you from helping.

Zulfi.

 

I think WBahn must improve . . . . If my reply is wrong, he has to tell me where I am wrong instead. I am not asking him the answer. But he should not come up with another set of questions.

I strongly disagree with your assessment.

Suppose someone is studying arithmetic in elementary school and asks you for help on a problem: calculating 24 + 17. You could simply tell them the answer, but then they wouldn't have learned anything except how to answer that particular problem. To help them understand the more general problem of adding two multi-digit numbers, you'd first like to know where their misunderstanding lies. You might ask them to attempt the calculation, describing each step of the process as they proceed. Begrudgingly, they do so, revealing a confusion in the concept of carrying digits.

Knowing the source of the misunderstanding, you take a detour from the original problem and focus on what it means to carry "extra" digits in positional arithmetic. You might ask them to add 7 + 4, two single-digit numbers, and reflect on how many digits the answer requires. This seems like a waste of time to them, but you gently suggest that the effort will help them in solving any such problem. More still, truly understanding how and why we use positional number notation will completely demystify and ground the algorithmic recipes we use to solve arithmetic equations. What once were a bunch of seemingly meaningless steps to be memorized, will become the logical and necessary parts of an elegant machine. "You will see these problems like a master mechanic looks at an engine", you tell the student.

Then, someone else comes along and announces "24 +17 = 41, just make sure you carry the 1 to the left." The student says "Oh, perfect, thanks!" and gives you a look saying, Why did you waste my time?

In a few weeks, the student comes back asking about 124 + 117.