Time complexity of 'if' with multiple conditions

Question

I'm confused whether the time complexities of these two codes are same or different.

code1

#include<iostream> using namespace std; bool check(int a[]) { if(a[0]==1 && a[1]==1 && a[2]==1 && a[3]==1 && a[4]==1 && a[5]==1 && a[6]==1) return true; return false; } int main() { int a[7] = {1,1,1,1,1,1,1}; if(check(a)) cout<<"yes"<<endl; else cout<<"no"<<endl; return 0; }

code 2

#include<iostream> using namespace std; bool check(int a[]) { for(int i=0;i<7;i++) { if(a[i]!=1) return false; } return true; } int main() { int a[7] = {1,1,1,1,1,1,1}; if(check(a)) cout<<"yes"<<endl; else cout<<"no"<<endl; return 0; }

when I checked it online at http://www.lizard.ws it showed that code 2 has less time complexity than code 1. If true why? please someone give me the reason.

raven404 · Accepted Answer · 2020-05-07 10:11:28Z

In your case you're doing the same kind of thing for every item in the input once.
if..else is just one normal statement you do to each item once. It does neither increase nor decrease the runtime/complexity. Your algorithm is O(1). If as per lizard.ws 2 code is efficient it might be taking the factor that everytime in code 1 u have to check all the condition despite of any single while in code 2 ur checking only one

What do you mean with in code 1 u have to check all the condition despite of any single? If a[0]==1 is false none of the following has to be checked. In both the cases you will only check until the first comparison is false.

Nikola Dim · Accepted Answer · 2020-05-07 10:02:29Z

1

Time complexities of both examples are the same. Especially since you don't have any variable number of elements, but fixed number. Since it's a fixed number, the time comlexity is O(1), but if the numElements (which is hardcoded at 7) were variable, the time complexity would be O(n).

answered May 7, 2020 at 10:02

Nikola Dim

8469 silver badges21 bronze badges

2 Comments

Vamsi Over a year ago

But in the website it says the complexity of code 2 is less than code 1.

Nikola Dim Over a year ago

I haven't used that webiste, but don't take its word for granted. You can try submitting tests for bigger numElemenst, e.g. 100000. The worst case for both examples is the same and there is no doubt: in the worst case they both check each element in array once

Collectives™ on Stack Overflow

Time complexity of 'if' with multiple conditions

2 Answers 2

1 Comment

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Related