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

Question

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.

That won't compile, to start with. Always start with valid code... — Jon Skeet, Sep 05 '16 at 14:54
The question doesn't really pertain to operational code... I'll change it however, thanks. — Ari K, Sep 05 '16 at 14:56
@MuratK. OP just clarified that this is just a snippet for time-complexity analysis, rather than execution. — Prateek Gupta, Sep 05 '16 at 15:01
Sorry I cannot change it to compilable code right this minute but I will definitely come back later. — Ari K, Sep 05 '16 at 15:08

score 0 · Accepted Answer · edited May 23 '17 at 12:32

0

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)

edited May 23 '17 at 12:32

Community

1
1

answered Sep 05 '16 at 15:04

Prateek Gupta

538
2
10

Thank you very much! Will check out these resources. Why would the complexity be O(n) and not say, O(3n+2). – Ari K Sep 05 '16 at 15:08
1

Constants are omitted during asymptotic analysis. – Prateek Gupta Sep 05 '16 at 15:11
@AriK If you are satisfied with my answer to your question, please mark it as accepted. Thanks. – Prateek Gupta Sep 05 '16 at 15:14

score 0 · Answer 2 · answered Sep 07 '16 at 22:46

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

No because Big-O is not about code operations at the level that you are counting them. To quote this descent page about Big-O:

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm. Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

In your case you have:

O(N) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set.

As N increases, your for loop increases linearly so your code is O(N).

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

2 Answers2