c++ - Figuring out the algorithmic complexity of my Program in Big-O Notation -
i have created program binary search on order list user enters, , outputs desired value want search in list. problem have find algorithmic complexity in big-o notation each part of code time complexity of it, however, not great @ figuring out big-o notation. if possible explain how it, etc. here's code , have tried figure algorithmic complexity lines, if did wrong please correct me.
#include<iostream> #include<vector> using namespace std; int binarysearch(vector<double> uservector, int, int); int main() { int size; // o(1) int i; //o(1) int desirednum; // o(1) cout << "how many values want enter: "; // o(1) cin >> size; // o(1) vector<double> uservector(size); (i = 0; < size; i++) { cout << "enter value: "; cin >> uservector[i]; } cout << "what value looking for: "; // o(1) cin >> desirednum; // o(1) int location = binarysearch(uservector, size, desirednum); if( location > -1) cout << "the value " << desirednum << " found @ index " << location << endl; // o(1) else cout << "the value not found in list. \n"; // o(1) system("pause"); return 0; } int binarysearch(vector<double> uservector, int size, int value) { int low, mid, high; low = 0; high = size - 1; while(low <= high) { mid = ((low + high) / 2); if(value == uservector[mid]) { return mid; } else if(value > uservector[mid]) low = mid + 1; else high = mid - 1; } return -1; }
you've got right, degree. other, don't.
int main() { int size; // o(1) int i; //o(1) int desirednum; // o(1) these aren't instructions, declarations. don't take run time @ all.
cout << "how many values want enter: "; // o(1) you shouldn't counting things happen prior start of algorithm @ all.
cin >> size; // o(1) vector<double> uservector(size); (i = 0; < size; i++) { cout << "enter value: "; cin >> uservector[i]; } cout << "what value looking for: "; // o(1) cin >> desirednum; // o(1) you shouldn't counting things happen prior start of algorithm @ all.
int location = binarysearch(uservector, size, desirednum); if( location > -1) cout << "the value " << desirednum << " found @ index " << location << endl; // o(1) else cout << "the value not found in list. \n"; // o(1) system("pause"); return 0; } ok, here starts part want have complexity for.
int binarysearch(vector<double> uservector, int size, int value) { int low, mid, high; low = 0; high = size - 1; while(low <= high) { mid = ((low + high) / 2); if(value == uservector[mid]) { return mid; } else if(value > uservector[mid]) low = mid + 1; else high = mid - 1; } return -1; } you're halving distance target each iteration, giving log2(n) complexity.