Question

Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$. From the book "Cracking the coding interview":

"In industry (and therefore in interviews), people seem to have merge Θ and 𝑂 together. Industry's meaning of big O is closer to what academics mean by Θ , in that would be seen as incorrect to describe printing an array as $O(n^2)$. Industry would just say this is O(N)"

In an interview context, would it be considered ok to say $\Theta$ instead of O?
If the interviewer is asking : "What's the Big O of this algorithm?", is it alright to answer :"The time complexity of this algorithm is $\Theta$(n)"?
I'm wondering if most interviewers would think I'm trying to outsmart them by saying that. But I don't feel comfortable by replacing O by $\Theta$ since they don't have the same meaning.

Was it helpful?

Solution 3

Here is an answer from reddit that I found the most useful:

I guess I would say, if someone says, "what's O of insertion sort?", you want to say "it's $O(n^2)$". Sure it's not precisely the same thing as saying that it's "$\Theta(n^2)$ in the worst case", but it's a convention that everyone understands, and it takes less time to get the words out of your mouth.

OTHER TIPS

I think its fine. It just shows the interviewer you actually know what the real meaning of big-O and theta are. Just make sure its actually true (the $\Omega$ part) when you have a complicated algorithm and you have used some inequality for big-O complexity proof.

If you mention big-theta many interviewers will think you are wrong because they never heard of it. If you then start debating it, then you fail at what the interview is primarily about: Convincing the interviewer that they want to work with you.

Question: You check if X is a prime by testing divisibility by 2, 3, 5, 7, 11 etc. What is the Big-O of the time complexity? If you answer “it’s big-Theta”, what will my opinion of you be?

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top