big o - Determining the time complexity of this portion of code -
//assume these 2 arrays given user , don't know // contents int a[5] = {1,0,2,1,0}; // (1) operation int y[5] = {0,0,1,1,2}; // (1) int n = 5; // (1) for(int i=0; i<n; i++){ // (n) operations if(a[i]!= y[i]){ // (n) operations in worst case..? cout << "hello" << endl; // (n) operations in worst case? } }
i confused nested statements, know loop occurs "n" times , proportional input size. however, if statement proportional "n" in case well? cout statement proportional "n". mean piece of code has running time of o(n^3)..? confused constant operation , isn't in terms of proportionality input size.. assuming worst case here no items match..
you can calculate like:
for(int i=0; i<n; i++){ if(a[i]!= y[i]){ cout << "hello" << endl } }
you can if(a[i]!= y[i])
1 operation complexity o(1) , in worst case executed n times, once in each iteration. same cout
.
so 2 constant operations in each iteration.
o(n)*(o(1) + o(1)) = o(2*n) = o(n)
Comments
Post a Comment