If you want to make money online : Register now

Big-O comparison different arrangements of similar code

, , No Comments
Problem Detail: 

The following code should have a run time of $O(N)$,

int min = INTEGER.MAX_VALUE; int max = INTEGER.MIN_VALUE;  for (int x : array) {     if (x < min) min = x;     if (x > min) max = x; } 

but what about the following code?

int min = INTEGER.MAX_VALUE; int max = INTEGER.MIN_VALUE;  for (int x : array) {     if (x < min) min = x; } for (int x : array) {     if (x > min) max = x; } 
Asked By : Anonymous Human
Answered By : Anjo

Its O(N). When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

for (int i = 1; i <=m; i += c)  {           // some O(1) expressions } for (int i = 1; i <=n; i += c)  {         // some O(1) expressions } 

Time complexity of above code is O(m) + O(n) which is O(m+n) If m == n, the time complexity becomes O(2n) which is O(n).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63983

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback