1
$\begingroup$

I'm trying to gain a better understanding of Big O.

Here is something that I'm unsure about. Say we have an array containing N elements that is inputted by the user. From my understanding iterating over each element from this array gives O(n) as we are looping over the array N times.

Now we do the same thing, we iterate over the array N times but only store, for example the number 3 from the array, into another array. Which we then loop over that array. What would the full equation for this algorithm or is it the case that the final result will always be O(n) and so we can completely ignore the rest?

Example:

firstArray = [1,1,1,2,2,2,2,3,3,3,6,7,8]
secondArray = []
for i=0 to firstArray.length()
   secondArray.add(firstArray[i])

for i=0 to secondArray.length()
   secondArray[i] += 10
   print(secondArray[i])

What confuses me is how we represent the second array, as it can be different each time the code is executed.

$\endgroup$

1 Answer 1

2
$\begingroup$

In doing running-time analysis, we often assume the worst-case. That is, what scenario will lead to the maximum possible running-time. As for your question about the second array, you can assume that in the worst-case, everything from the first array was transferred to the second array. That is, in the worst-case the second array has $n$ elements. In your example, assume that all indices of the first array contains the element 3, thus everything will transferred. However, note that the running-time of the second loop, will depend on what you are doing inside.

As for the total running-time of the two loops, you can add up the time taken by the first loop and the second loop, again assuming the worst-case.

As a final note, it is important that you also understand the cost of the add operation in the first loop. It is often expensive to insert a new element at the beggining of the array since that would require moving all elements already in it, which will lead to an $O(n^2)$ total time for the first iteration, in such case. This can be improved, if you insert elements at the end instead, so no elements are moved, which will guarantee an $O(n)$ total running-time for the first loop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.