0

Below are two ways I could traverse any array:

  1. Using for loop a variable would traverse from starting to end of array.
  2. Using while loop 2 variables would traverse from opposite direction and meet in between.

How would the time complexity vary, would it be reduced in second case or it would be same?

Improve this question
4
  • 1
    It's the same in both cases because you're still visiting each array element only once. Commented Aug 23, 2020 at 3:00
  • @Dai Isn't the time complexity be smaller by a factor of 2? The space complexity will be the same but theoretically the 2nd method should take O(n/2)(not taking into account rounding it to O(n), of course) Commented Aug 23, 2020 at 3:02
  • Think about it this way -> it's not actually the retrieval of elements that's "costing" anything, it's whatever you're doing with the elements of the array that has a cost. That cost still has to be paid once for each element, even if you pull two elements out then operate on them separately. Commented Aug 23, 2020 at 3:02
  • @Alex.Kh Big-O notation (and time-complexity in general) is only concerned with a function's "order" (growth-rate), so if you have an O(1) algorithm that always takes exactly 1,000,000 years on today's CPUs and and another algorithm for the same problem that runs in O(n^2) time (but which runs in only a few milliseconds due to some CPU optimization that makes each operation very cheap, but still needs to run n^2 times) then that doesn't change their time-complexity and the million-year algorithm is still less-complex in time. Commented Aug 23, 2020 at 7:46

1 Answer 1

Reset to default
1

Of course the same. Both are O(n), in fact there is no way to traverse an array faster than O(n).Even if you tarverse from opposite direction, you still have to visit each element once.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

that's because you did't do much things in your loop,so the loop time become the most time-consuming part. But in real world,you usually have to do some processing for each element, in that case the while loop won't save much time.
"in fact there is no way to traverse an array faster than O(n)" - I'm going to be a smart-arse here: if we're talking about arrays (or vectors or tuples) specifically then in the case where their length n is constrained to n <= hardware-units then O(1) algorithms exist (e.g. SIMD and its implementations in SSE). I argue these are true O(1) algorithms because the growth-rate of the algorithm is zero and when n is too large the algorithm literally cannot work. Jus' sayin' (in practice SIMD as-used in algorithms ends up supporting arbitrary n so they're O(n), though)

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.