Search code examples
time-complexitybig-ospace-complexity

Time and space complexity of these codes


I just learned about time and space complexity and I dont think I am really grasping them. I will put up some codes would would ask kindly if some of you could tell me their time and space complexity and how you decide them.

Code 1

public static int nmKomplex(int n, int m){
     int sum = 0;
     for(int i = 1; i < n; i++)
       for(int j = 1; j < m; i++)
         sum += i * j;
     return sum;
}

Code 2

public static void Schleife3(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++)
      for(int j = 1; j<= n; j++)
         sum += i * j;

    for(int i = 1; i <= n; i++)
       sum += i
} 

Solution

  • First code:

    public static int nmKomplex(int n, int m){
         int sum = 0;
         for(int i = 1; i < n; i++)
           for(int j = 1; j < m; i++)
             sum += i * j;
         return sum;
    }
    

    TL:DR Time Complexity O(n * m) | Space Complexity O(1)

    A loop that goes from i = 1 to n times another loop that goes from j=1 to m. For n > 1, the first loop performs (n - 1) iterations, times the second loop which performs (m - 1) iterations. Hence, the double loop executes nm - n - m + 1 iterations, which can be represented by a time complexity of O(n * m).

    The space complexity is O(1) (i.e., constant) since an increase in either the n and m values does not reflect in an increase of the space used.

    Second code:

    public static void Schleife3(int n){
        int sum = 0;
        for(int i = 1; i <= n; i++)
          for(int j = 1; j<= n; j++)
             sum += i * j;
    
        for(int i = 1; i <= n; i++)
           sum += i
    } 
    

    TL:DR Time Complexity O(n^2) | Space Complexity O(1)

    For n > 1, the first loop performance n iterations times the second loop which also performances n iterations plus the third loop which also performance n iterations. Therefore, time complexity of n^2 + n, which can be represented by O(n^2).

    The space complexity is O(1) (i.e., constant) since an increase in either the input n does not reflect in an increase of the space used.