Big O question

Question

If I have the following code:

IterateArray(object[] array)
{
    for(int i=0; i<array.length; i++)
    {
        Dosomething(array[i]);
    }
}

and the Dosomething(object) method's time performance is O(log n), is the overall performance of IterateArray O(n) or O(n log n)?

Thanks.

Answer 1

It would be O(n log n)

You're doing an O(log n) performance operation n times, and multiplication holds with Big O, so O(n) * O(log n) = O(n log n)

It's important to note that there really need not be any distinction between m and n if you're looking at two different sized arrays. The reason being is that m and n are both constants, and they are asymptotically equivalent if you were to graph their growth rates.

Answer 2

O( n log n )

Think about it - you're performing a log n operation n times.

Answer 3

Hi

Since the 'for' loop iterates n (say the array length is n) times and in each iteration 'Dosomething' is executed, the overall performance would be O(n logn).

cheers

Answer 4

For each of your m objects, if the performance of DoSomething() is O(log n), then the total performance across all of your m objects would be O(m log n).

Answer 5

The short & somewhat wrong answer is O(n log n).

The long answer: It'd be more accurate to write it as O(n log m).

Unless DoSomething really DOES depend on the entire array, it looks like it's operating on a single element. So we distinguish this separately, using "m".