Big question about

Question

If I have the following code:

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

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

Thanks.

Answer 1

The short and somewhat incorrect answer is O (n log n).

Long answer: it would be more accurate to write it as O (n log m ).

If DoSomething really depends on the whole array, it looks like it works on a single element. Therefore, we distinguish this separately using "m".

Answer 2

That would be O (n log n)

You perform a performance operation O (log n) n times and multiplication is done using Big O, so O (n) * O (log n) = O (n log n)

It is important to note that there really is no need to distinguish between m and n if you are looking at two arrays of different sizes. The reason is that m and n are both constants, and they are asymptotically equivalent if you were to calculate their growth rates.

Answer 3

O (n log n)

Think about it - you perform the operation nn times.

Answer 4

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

Answer 5

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

amuses