Big o computation

Find the runtime of the code shown below:

int foo(int a[], int n) { int j = 0; for(int i = 0; i < n; ++i) { while(j < n && a[i] < a[j]) { j++; } } return j; } 

Input Format

Elements of the array each separated by a single space from the next.

Example:

5 4 3 2 7 8

Constraints

None

Output Format

One of the following

• O(log n)
• O(n)
• O(n log n)
• O(n^2)
• O(n^3)
• O(2^n)
• O(n^n)

Where n is the size of array a.

Given code for solution:

import java.io.*; import java.util.*;

public class Solution {

public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ } }