Ari K Ari K - 3 months ago 15
Java Question

Is my thinking for the total number of operations in the code-snippet below valid? (Big-O notation)

public class foo{
public static void main(String[] args){
int a = 1;
int b = 1;
int n = 4;

//Focus is on the below for-loop
for(int x=1,x<=n,x++){
c=a+b;
}
}
}


x=1 --> O(1) //One assignment statement

x<=n --> O(n+1) //checks n times and then a following time

x++ --> O(n) //increments n times

c=a+b --> O(4n) //increments n times, but the statement itself has four operations, LOAD A + LOAD B + ADD + STORE C

Now how would I combine these? i.e. Do I add, or multiply, and why?

Thanks in advance.

Answer

Your thinking is valid, but that is not BigOh To calculate BigOh you need Asymptotic analysis

There is an awesome answer by a university professor here, you should check out the last part of his answer.

Time complexity of your code would be O(n)