Compute Big O

Find the runtime of the code shown below:

In Java:

int quux(int n) { int a = 0; int b = n; int c; while (b - a > 0) { c = (a + b) / 2; if (c > rand()*n) { a = c; } else { b = c; } } return c; } 

In Python:

def quux(n): a = 0 b = n while (b - a > 0): c = (a + b) / 2 if (c > rand()*n): a = c else: b = c return c 

Input Format

N, the input to the function. Example:

10

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)

Sample Input 0

10 

Sample Output 0

O(n log n)

Given Code to write answer:

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. */ } }