CODEWITHSUNDEEP
javatimecomplexity-theory
N.Der
N.Der

Reputation: 41

Time complexity

I am trying to find the time complexity of these procedures but I am not sure if they are good.

I think this is O(n)

static void P1(int n ){
   for (int i=1; i<=n; i++) {
      Procedure();
}

I think this is O(n^2)

static void P2(int n) {
   for(int i=1; i<=n; i++) 
    for(int j=1; j<=n; j++)
      Procedure();
}

O(n)+O(n)

static void P3(int n) {
   for (int i = 1; i <= n; i++)
     Procedure();
   for (int i = 1; i <= n; i++)
     Procedure();
}

100+n+100?

static void P4(int n) {
   for ( int i = 1; i <= 100; i++)
     for (int j = 1; j <= n; j++)
       for (int k = 1; k <= 100; k++)
         Procedure();
}

O(n*i)?

static void P5(int n) {
   for ( int i = 1; i <= n; i++)
     for (int j = 1; j <= i; j++)
       Procedure();
}

?

static void P6(int n) {
   for (int i = 1; i <= n/2; i++)
     for ( int j = 1; j <= n/4; j++)
       for (int k = 1; k <= n/8; k++)
         Procedure();
}

Upvotes: 0

Views: 112

Answers (2)

Naveen Kakani
Naveen Kakani

Reputation: 1

Time complexity of 

static void P3(int n){
   for (int i = 1; i <= n; i++)
     Procedure();
   for (int i = 1; i <= n; i++)
     Procedure();
}

can be written as a function of O(2n) as we need to eliminate constants it becomes O(n)

Time Complexity of 

static void P4(int n) {
   for ( int i = 1; i <= 100; i++)
     for (int j = 1; j <= n; j++)
       for (int k = 1; k <= 100; k++)
         Procedure();
}

100+n+100 => O(n*100*100) => O(n)

Time complexity of 

static void P6(int n) {
   for (int i = 1; i <= n/2; i++)
     for ( int j = 1; j <= n/4; j++)
       for (int k = 1; k <= n/8; k++)
         Procedure();
}

is O(n^3)

Remember that we are not calculating the no.of instructions computer executes using time complexity. The Big-O just tells how our execution time varies with increase or decrease in input.

consider reading Time Complexity

Upvotes: 0

libik
libik

Reputation: 23029

If Procedure() is O(1), then :

I think this is O(n) correct

static void P1(int n ){
   for (int i=1; i<=n; i++) {
      Procedure();
}

I think this is O(n^2) correct

static void P2(int n) {
   for(int i=1; i<=n; i++) 
    for(int j=1; j<=n; j++)
      Procedure();
}

O(n)+O(n) correct, but O(n+n)=O(2n)=O(n)

static void P3(int n) {
   for (int i = 1; i <= n; i++)
     Procedure();
   for (int i = 1; i <= n; i++)
     Procedure();
}

100+n+100? false, it is multiplicated : O(100*n*100)=O(n)

static void P4(int n) {
   for ( int i = 1; i <= 100; i++)
     for (int j = 1; j <= n; j++)
       for (int k = 1; k <= 100; k++)
         Procedure();
}

O(n*i)? You cant use i it does not have exact value. If you look how much times inner loop is executed, it is 1+2+3+4+...+n-3+n-2+n-1, which is n*(n-1)/2, you can multiply it : n*(n-1)/2=n^2/2-n/2 which is assymptotically n^2/2-n/2=Theta(n^2)

The result is O(n^2)

static void P5(int n) {
   for ( int i = 1; i <= n; i++)
     for (int j = 1; j <= i; j++)
       Procedure();
}

n/2 * n/4 * n/8 = n^3/64 = O(n^3)

static void P6(int n) {
   for (int i = 1; i <= n/2; i++)
     for ( int j = 1; j <= n/4; j++)
       for (int k = 1; k <= n/8; k++)
         Procedure();
}

Upvotes: 2

Related Questions