-2

In a sample exercise, I was to check if all the elements in an array are identical to each other. THIS QUESTION IS NOT ABOUT THE MOST EFFICIENT WAY TO DO THIS. Rather, it is about these two solutions. 

 for(var i=0; i < set.length-1; i++)
  {
    if (set[i] != set[i+1]) // could have compared all elements to the firstelement instead of switching
    {
     isTrue=false;
    }

  }

This above algorithm compares each index to the index afterward. 

var firstIndex=set[0];
for(var i=0; i < set.length-1; i++)
{
  if(set[i] != firstIndex)
    {
        isTrue=false;
    }
 }

While this algorithm compares the current index to the first index. Although these algorithms are at least O(N). Does the difference in the comparisons affect the time/space complexity?

Ran
  • 333
  • 1
  • 4
  • 16
  • It would help efficiency if the condition was `i < set.length-1 && isTrue` so it stops when the first non–duplicate is encountered. – RobG Dec 14 '17 at 03:43
  • I'm preparing for an interview, and I was just trying to understand how to compute complexity based on given code. Would the big O be linear in either case? –  Dec 14 '17 at 03:48

2 Answers2

0

Space complexity: No change as you are not using any extra variable/data structure (firstIndex in the second snippet is not considered because it takes constant space).

Time Complexity: Little or No change. In both the snippets, you are doing a single comparison, but the first snippet will be little slower because array accessing is slower compared to direct variable access.

Ran
  • 333
  • 1
  • 4
  • 16
  • Okay, this is exactly what I was wondering. Would accessing the array repeatedly cause any change. Thank you! Do you know why this question got downvoted? –  Dec 14 '17 at 03:47
  • Also, Would the big O be linear in either case? –  Dec 14 '17 at 03:48
  • Big O is linear in both the cases for the reason that array access is not considered towards time complexity generally. – Ran Dec 14 '17 at 05:06
0

Well lets clear things up

Time complexity for both of them would be O(n). Space complexity is O(1).

Things like array index access or etc has no effect on the Big-O timne complexity.

Although these algorithms are at least O(N).

These are O(n) not atleast.

You can improve run time not time complexity by doing things like 

if(set[i] != firstIndex)
{
    isTrue=false;
    break; 
}
user2736738
  • 30,591
  • 5
  • 42
  • 56
  • Ah! Okay, from https://stackoverflow.com/questions/4915842/difference-between-time-complexity-and-running-time, I understand that the runtime is not generally known for most algorithms. In regards to scaling to larger inputs, does the runtime matter? –  Dec 14 '17 at 20:53
  • For scaling yes run time matters - but look then also you know the change you will have will be proportionate linearly. Any change will be linear if you scale this algo over large `n`. Not sure if you were asking this - but for runtime ofc there is variation over `n` but for complexity they belong to the same class.@NithinMoorthy – user2736738 Dec 15 '17 at 03:07