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

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -