For the list without repetitions of course the pseudocode is trivial:
x:= a_(10)
{output x}
It doesn't matter how large n is it still takes the same number of steps. Hence this is O(1).
For a list with repetitions, we will have to have the algorithm that potentially has to look at each element.
t:=0 {a counter for "clock ticks"}
i:=1
e:=0 { a counter representing numbers less than a_i in list}
while ( e<10 and i<n)
if a_i < a_(i+1) then e:=e+1
i:=i+1
end
if e=10 then x:=i
else x:=0
{x=0 means do not have 10 distinct elements}
If we input a_1, ..., a_n, we could let i run from 1 to n and test each a_i to see if it is the middle element. So given a_i, how will we test that? We just let j run from 1 through n and count how many of the a_j are less than and how many are equal to a_i. Think about which condition on these two numbers guarantees that the middle number of the ordered list will equal a_i. This algorithm is O(n^2).
value:=0 {this will be the middle element}
for i:= 1 to n
Less :=0 {number of elements less than a_i}
Equal := 0 {number of elements equal a_i}
for j:=1 to n
if a_j< a_i then Less:=Less +1
if a_j=a_i then Equal := Equal +1
end
end
Of course, f is 1-1, if whenever i< j, f(i) is not equal to f(j). That is, a_i is not equal to a_j. We need to look at each a_i and see if there is a j>i such that a_i=a_j. We might as well stop if this ever happens. Let me give two, they both have the same complexity. The first makes all comparisons hence there's no need to worry about worst case. I'll not analyse the second but you should (it might fool you since there's only one "while" loop and you might jump to the conclusion that it is O(n)).
value:=1 {switch this to 0 if it is not 1-1}
for i:=1 to n-1
for j:=i+1 to n
if a_i = a_j then value:=0
{I don't think I needed "begin-end" here}
The complexity analysis: For each i, what do we do? We let j go
from i+1 to n. This is (n-i) steps. Therefore, considering all i, we get the
sum:
(n-1) + (n-2) + ... + (n-(n-1))= 1+2+...+(n-1)
SIGMA { k : k=1,...,n} = (n*(n+1))/2
This sum is (SIGMA {k: k=1,..., n} ) - n = n * (n+1)/2 -n
= n ( (n+1)/2 - 1) = n( (n+1)/2 - 2/2) = n ( (n-1)/2)
We could certainly do (1+...+(n-1) = (n-1)( (n-1)+1)/2 directly but I
wanted to give a little practice with SIGMA.
Of course n*(n-1)/2 is O(n^2).
Here is the second:
j:=2
While (i < n and a_i < > a_j){common symbol for not equal}
if j < n then j:=j+1
else
i:=i+1
j:=i+1
end
value:=0
hits:=1
i:=1
while hits<> 2 {remember this mean not equal}
hits:=1
j:=i+1 {oops first version started at i+1}
while (j<= n and hits< 3)
if a_i=a_j then hits:=hits+1
j:=j+1
end
end
S:= 0 {initialize sum}
for i:=1 to n
if x=a_i then S:=S+i
while a< 0
a:= a+m
while a> (m-1)
a:=a-m
{that's it, a now has value a mod m}
The complexity is O(a/m). Only one of the while loops is actually performed. It takes roughly a/m steps to complete.
Actually, all I had in mind here is that you remember that the Euclidean algorithm to compute gcd(a,b) is O(log(min(a,b))). So all we do is have an algorithm written, call it Euclid, which does this. Then here is the simple algorithm:
if m=1 then stop {there's no point}
for i:=1 to m-1 {we know m is not relatively prime}
d:= Euclid(i,m)
if d=1 then Print(i)
end
For O(m^2), test each b between 0 and m, one by one. For each such b what do we have to do? Just let x run from 0 to m-1 to see if a*x=b (mod m). This is just an m loop in an m loop, so O(m^2). We are assuming that we can multiply or else finding if a*x=b (mod m) would add an additional power to the complexity.
For O(m log(m)): use our theory. It's actually easier than what I was thinking. We know that there is a solution just if b is a multiple of gcd(a,m). In O(log(m)) steps we've computed d =gcd(a,m). Then we just list the multiples of d that are less than m. This second loop is not inside the first loop (finding the gcd), it comes after. Hence this algorithm is O(log(m)+m), and so just O(m) (even O(log(m)+m/d), since all we've got to do is compute d, d+d, d+d+d, ...
Method 1: First compute the largest and smallest elements. Then, let i run from 1 to n. Set two counters, Less and Equal to 0. For each i, we have an inner loop j running from 1 to n. If a_j < a_i, increment Less by 1. If a_j = a_i, increment Equal by 1. This ends the j loop. Think of a test using Less and Equal to determine if a_i is (or something equal to it is) the 10-th largest in the list. We neglected to ignore the smallest and largest elements so fix that up in the "IF" statements. Then go to the next value of i.
Method 2: Again compute the largest and smallest elements. Now just run through the list at most 10 times, each time finding the next smallest element (counting repetitions).
Method 3: Again compute the largest and smallest elements. This time, set b_1, b_2, ..., b_10 equal to a_1, ..., a_10. The idea is that b_1, ..., b_10 should end up as the first 10 elements of that final list mentioned in the question. Starting with i = 11, run through the list just once. If a_i is more likely to belong in that list than some b_k, then b_k:= a_i.
Compare the complexities of the methods.
I won't write pseudocode but here's the complexities:
Method 1: n + n + n^2, hence O(n^2) {I realize there was no need to compute
the largest}
Method 2: n + n + (n+n+n+(7 more)) is O(n)
Method 3: n + n+ 10n
The difference between 2 and 3 is that 2 does a loop 10 times, while 3 does one loop n times but does 10 things in each loop.