0

Find the time complexity and big O of following code. I am confused about what will be the time complexity of if else statements and other bar(a) and foo(a) function. Some friends are saying its time complexity is O(n^2) and some says its time complexity will be O(n). I also think that the time complexity of the following code will be O(n) because there is a return statement in the for loops which will make the time of both foo and bar function as O(1) and main for loop will run n time so time complexity will be O(n).

// Sample Code

public static void main(String args[]){
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int sum = 0;
    for(int i=0 ; i<n ; ++i){
        if(i%2 != 0){
            sum += foo(i , n) + foo(1+i , n);
        }
        else{
            sum += foo(i , n) + bar(i , n);
        }
    }    
}

-

static void bar(int a , int n){
for(int i=0 ; i<n ; ++i){
    for(int j=0 ; j< i ; ++j){
        return a*(i+j);
    }
  }
}

-

static void foo(int a , int n){
for(int i=0 ; i<n ; ++i){
        return a*i;
   }
}
Muhammad Umar
  • 130
  • 1
  • 10
  • Possible duplicate of [How can i convert Integer value to decimal value?](https://stackoverflow.com/questions/3707731/how-can-i-convert-integer-value-to-decimal-value) – vinS Oct 30 '17 at 14:04
  • 1
    Check out this resource and then elaborate on exactly where you are stuck https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – Doug Clark Oct 30 '17 at 14:10
  • Sounds like homework. What have you tried so far? Share your thoughts. There do you get stuck? – MrSmith42 Oct 30 '17 at 14:30
  • I'm voting to close this question as off-topic because it is not clear what the problem of the user exactly is. It also shows no effort to solve the problem itself. – MrSmith42 Oct 30 '17 at 14:32
  • Right, the complexity is O(n) because of the returns. But a super-duper optimizer might see that foo and bar always return 0 so that there is no use to execute anything ! –  Oct 30 '17 at 16:21

2 Answers2

1

Since you expressed your algorithm using an iterative paradigm, all you have to do is count the number of operations.

The complexity of bar is O(n^2), because you have n * (n + 1) / 2 operations of the type "add i, j, then multiply by a".

The complexity of foo is O(n) (n operations of the type "multiply by a").

In your main loop, half of the operation will call foo twice, which yields (n / 2) * n operations which is O(n^2). The second half of the iterations will call foo then bar, which yields (n / 2) * [n + n * (n + 1) / 2] that is to say 0.25.n^3 + 0.75.n^2 which is O(n^3).

Therefore, the overall complexity of your loop is O(n^3). This is generally referred to as the time complexity of your algorithm (even though we counted the number of operations - the intuition behind it is to consider a set of unit of operations and acknowledge each of those will take a constant amount of time. In our case, we chose the arithmetic operations + and *).

We can also analyse your algorithm from the perspective of memory consumption. In your case, the memory consumed is constant whatever the value of n is. This is why we would say that the space complexity is O(1) with respect to n.

Edit: I though the "premature" return in foo and bar was a typo. If you don't loop, then the complexity of foo and bar is O(1), and your main loop is O(n).

Alexandre Dupriez
  • 3,026
  • 20
  • 25
  • Hy Alexandre Duriez there is an return statement in both foo and bar function ( in for loops ). So i think there time complexity should be O(1) – Muhammad Umar Oct 30 '17 at 15:01
  • Ah right - I though it was just a mistake. If you don't loop, then yes the complexity of `foo` and `bar` is `O(1)`, and your main loop is `O(n)`. – Alexandre Dupriez Oct 30 '17 at 15:04
0

foo() -> O(n) because it goes from i = 0 -> n:

bar() -> O(n^2) because it from j = 1 + 2 + 3 + ... + n which is O(n^2), as follows:

For main() you are going from i = 0 -> n, and you are calling foo(n) twice every even value of i. You are also calling foo(n), but thats O(n) which does is not the worst case, so we do not care.

Considering the worst case bar(n), being called n/2 times (every other form 0 to n):