Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

All Questions

Tagged with
3
votes
1answer
30 views

Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
0
votes
1answer
37 views

How to compare an element with other elements within an array efficiently for a condition

I need to compare each index with one another and associated array value as well. For example, ...
2
votes
2answers
926 views

Proving at least $n-1$ comparisons are needed to test if an array is sorted

so I need to prove the following: Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$. The ...
5
votes
3answers
4k views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
0
votes
0answers
881 views

Pseudocode for checking if two arrays contain the same elements?

I'm not so much confused as to write the actual code as I am to write the pseudocode. To determine if two arrays of the same size contain the same elements, I know you would need two for loops, then ...