asked on

C# Programming

I have a set of 100,000 random integers. How long does it take to determine the maximum value within the first 25,000, 50,000 and 100,000 integers? Will processing 100,000 integers take 4 times longer than processing 25,000?

Here is my C# code:

Random radom = new Random();

int randomNumber = 0;

DateTime dtNow = DateTime.Now;

for (int i = 0; i < 100000; i++)
{
    // Search 25000
    //randomNumber = radom.Next(1, 25000);

    // Search 50000
    // randomNumber = radom.Next(1, 50000);

    // Search 100000
    randomNumber = radom.Next(1, 100000);
}

Console.WriteLine(randomNumber);
Console.WriteLine(dtNow.Second);
Console.ReadLine();

Open in new window

Am I do it right? How to calculate the time that I used to determine the maximum value?

Bill Prew

Since the set of random integers will not be in any order you essentially have to search the entire list to find the maximum. As a result the time it will take is On meaning order n, it's proportional to the number of items to be searched.

And yes, since it is linear with regard to the number of integers, then if there are 4x the number of integers, the time will be 4x.

»bp

ASKER CERTIFIED SOLUTION

David Johnson, CD

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Gustav Brock

Neat, David, but for repeated calls I receive results like these with rising times only:

Maximum Value is 2498 Search 2500 took: 286
Maximum Value is 4996 Search 5000 took: 532
Maximum Value is 9993 Search 10,000 took: 986
Using For Each
Maximum Value is 2498 Search 2,500 took: 107
Maximum Value is 4996 Search 5000 took: 208
Maximum Value is 9993 Search 10,000 took: 413

Open in new window

It is strange that method Max is that slow.

ste5an

It is strange that method Max is that slow.

It's the at least the function overhead for calling the Max() method. The loop on the other hand gets inlined.
I don't have another disassembler besindes ILDASM at hands right now, so I guess the documentation is correct:

The Max(IEnumerable<Int32>) method uses the Int32 implementation of IComparable<T> to compare values.

Which means further function calls.

Gustav Brock

That makes sense.

kaufmed

@David

Logically Bill is correct but sorting 10,000 items is trivial in today's computing world

Sure, it's trivial to humans--because our processors are much faster now--but that doesn't mean that there's any less work being done. Faster processors don't change the algorithms used to do the sorting/searching. As such, there's still real work involved in sorting the list, and you incur the cost of that work at least the first time you sort. Algorithm complexity is usually what one focuses on when trying to determine an optimal solution to sorting/searching.