-1
$\begingroup$

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;
}
$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – Raphael
    Commented Sep 28, 2016 at 6:09

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
1

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