Credit Suisse Interview Question
Tech LeadsCountry: India
Interview Type: Phone Interview
O(f(n)) means that our algorithm's running time is <= cF(n) for some C for all n>n1
BigTheta(f(n)) means our algorithms running it c1f(n) <= our algorithms running time <= c2f(n) for some c1 and c2 for all n>n1.
In other words O(f(n)) is an upper bound on how slowly our algorithm may run.
Big Theta says that the running time of our algorithm is bounded above AND below by some multiple of f(n). So no, big theta is not the average running time. It's the running time in all cases give or take a constant multiple.
i.e. Merge Sort is Theta(nlogn) because it takes nlogn no matter the input. Quicksort is O(n^2) but NOT Theta(n^2) because it may not take n^2( and usually doesn't) depending on the input.
Big Theta is not the average case...
Yes O(f(n)) says that our algorithm is bounded above by some constant multiple of f(n) such that it cannot run slower than it.
Big Theta however is a tighter bound. It says that our algorithm cannot run slower than a constant f(n) but it also cannot run FASTER than some constant times f(n). For example mergesort is big theta(nlogn) because it takes nlogn no matter the input. While Quicksort is O(n^2) but can run in nlogn time in most cases. Thus it is NOT Big Theta(n^2).
In mathematical terms: g(n)=O(f(n) implies g(n) <= c*f(n) for some constant c for all n past some n_0
and bigTheta implies c_1*f(n) <= g(n) <= c_2*f(n) for some constants c1, c2 for all n past some n_0.
Big-O is Worst case analysis of an algorithm
- Anonymous June 10, 2015Big Theta is Average case analysis of an algorithm
-Bala