## Credit Suisse Interview Question for Tech Leads

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
0
of 0 vote

Big-O is Worst case analysis of an algorithm
Big Theta is Average case analysis of an algorithm

-Bala

Comment hidden because of low score. Click to expand.
0

FALSE.
g = O(f(x)) means "g can be at most as big as f(x)"
g = Theta(f(x)) means "g is in the same order of magnitude as f"

Comment hidden because of low score. Click to expand.
0
of 0 vote

Big-O is Worst case analysis of an Algorithm
Big Theta is an Average case analysis of an Algorithm

Comment hidden because of low score. Click to expand.
0
of 0 vote

Big O -- worst case Theeta - average case

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.