Big O Problem

BigO.java

void foo(int[] array)
{
  int sum = 0;
  int product = 1;
  for(int i = 0; i < array.length; i++)
  {
    sum += array[i];
  }  
  for(int i = 0; i < array.length; i++)
  {
    product *= array[i];
  }  
  System.out.println(sum + ", " + product);
}
// foo 함수의 수행 시간 복잡도는?

void printPairs(int[] array)
{
  for(int i = 0; i < array.length; i++)
  {
    for(int j = 0; j < array.length; j++)
    {
      System.out.println(array[i] + "," + array[j]); 
    }
  }
}
// printPairs 함수의 수행 시간 복잡도는?


void printUnorderedPairs(int[] array)
{
  for(int i = 0; i < array.length; i++)
  {
    for(int j = i + 1; j < array.length; j++)
    {
      System.out.println(array[i] + "," + array[j]);
    }
  }
}
// printUnorderedPairs 함수의 수행 시간 복잡도는?

void printUnorderedPairs(int[] arrayA, int[] arrayB)
{
  for(int i = 0; i < arrayA.length; i++)
  {
    for(int j = 0; j < arrayB.length; j++)
    {
      if(arrayA[i] < arrayB[j])
      {
        System.out.println(arrayA[i] + "," + arrayB[j]); 
      }
    }
  }
}

//printUnorderedPairs 함수의 수행 시간 복잡도는?

void reverse(int[] array)   
{
  for(int i = 0; i < array.length / 2; i++)
  {
    int other = array.length - i - 1;
    int temp = array[i];
    array[i] = array[other];
    array[other] = temp;
  }  
}

// reverse 함수의 수행 시간 복잡도는?


boolean isPrime(int n)
{
  for(int x = 2; x * x <= n; x++)
  {
    if(n % x == 0)
    {
      return false; 
    }
  }
  return true;
}

// isPrime 함수의 수행 시간 복잡도는?

int fib(int n)
{
  if( n <= 0 ) return 0;
  else if(n == 0) return 1;
  return fib(n - 1) + fib(n - 2);
}

// fib 함수의 수행 시간 복잡도는?

void allFib(int n)
{
  for( int i = 0; i < n; i++)
  {
    System.out.println(i + ":" + fib(i)); 
  }
}

int fib(int n)
{
  if( n <= 0 ) return 0;
  else if(n == 0) return 1;
  return fib(n - 1) + fib(n - 2);
}

// allFib 함수의 수행 시간 복잡도는?


void cachedFib(int n)
{
  int[] memo = new int[n + 1];
  for(int i = 0; i < n; i++)
  {
    System.out.println(i + ": " + fib(i, memo));  
  }
}

int fib(int n, int[] memo)
{
  if(n <= 0) return 0;
  else if(n == 1) return 1;
  else if(memo[n] > 0) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

// cachedFib 함수의 수행 시간 복잡도는?

int powerOf2(int n)
{
  if( n < 1 )
  {
    return 0; 
  }
  else if(n == 1)
  {
    System.out.println(1);
    return 1;
  }
  else
  {
    int prev = powerOf2(n / 2);
    int curr = prev * 2;
    System.out.println(curr);
    return curr;
  }
}

// powerOf2 함수의 수행 시간 복잡도는?