CODEWITHSUNDEEP
javaalgorithmbig-o
Cainster
Cainster

Reputation: 29

BIG O Analysis of Loops

Can someone provide examples of loops that are PolynomialO O(n^2) , Exponential O(2^n) , and Factorial O(n1). I can't seem to wrap my head around it.

I understand the concepts of
O(log n)for (int i=0; i<=10; i=i*2) OR for (int i=0; i<=10; i=i/2)
O(n)for (int i=0; i<=10; i++)or (int i=10; i<=0; i--).
O(n^2) `

for (int i=0; i<=10; i++)
{
    for (int i=0; i<=10; i++)
    {
      //DO SOMETHING
    }
}

Upvotes: 0

Views: 168

Answers (2)

Arman
Arman

Reputation: 655

O(n^2):

int count = 0;
for (int i = 0; i < n; i++){
  for (int j = 0; j < n; j++){
    count++;
  }
}

This is pretty simple, for every nested loop you will increase your power. So if you had 3 for loops instead of two, then it would be O(n^3)

O(2^n): 

public int fibonacci(int n){
    if (n<= 1) return n;
    return fibonacci(n- 2) + fibonacci(n- 1);
}

For every iteration of this method, two other "branches" will be created (until n<=1) since it has two recursive calls. So the growth doubles for every iteration.

O(n!):

public int factorialRuntime(int n) {
  int count = 0;
  for(int i=0; i<n; i++) {
    count += factorialRuntime(n-1);
  }
  return count;
}

This example was pulled from here.

Upvotes: 1

Stephen C
Stephen C

Reputation: 718926

A more obviously O(2^N) example is:

public int count2PowerN(int n) {
  if (n <= 1) {
     return n;
  } else {
     return count2PowerN(n - 1) +  count2PowerN(n - 1);
  }
}

Notes:

  1. O(2^N) is equivalent to any O(c^N) where c is a constant. It is conventional to use e as the nominal constant; i,e O(e^N)
  2. you cannot get super-polynomial complexity with simple nested loops. You need either recursion or a dynamic data structure.

Upvotes: 1

Related Questions