Running Time Analysis and Empirical Measurement
- when the big-O complexity is the same as big-Omega complexity, that means it's a tight bound -> big-Theta.
- tricky example
void tricky(){
int operations = 0;
while(n>0){
for(int i=0; i<n; i++){
cout<< "something"<<endl;
}
n/=2;
}
}
first while loop: n times
second while loop: n/2 times
third while loop: n/4 times
...
total: n + n/2 + n/4 + ....
-> O(n)
The below example can be applied to a BST!