Algorithm design: θ(f(n)) - help explaining my answer I am studying algorithm design and need some help explaining my (correct) answer to the following question: Assume that T(n)=Θ(n2). Can we say that for every input size n, our algorithm will perform a maximum of 10n3 operations? Why? My answer, is as follows: No, because by definition: T(n) is Θ(f(n)) only if T(n) is both O(n) and Ω(n). i.e. c1⋅f(n)≤T(n)≤c2⋅f(n) I was told that whilst the answer is correct, the explanation is not. Can somebody explain to my why this is the case?

Sasha Hess

Sasha Hess

Answered question

2022-09-05

Algorithm design: θ(f(n)) - help explaining my answer
I am studying algorithm design and need some help explaining my (correct) answer to the following question:
Assume that T ( n ) = Θ ( n 2 ). Can we say that for every input size n, our algorithm will perform a maximum of 10 n 3 operations? Why?
My answer, is as follows:
No, because by definition: T(n) is Θ ( f ( n ) ) only if T(n) is both O(n) and Ω ( n )
c 1 f ( n ) T ( n ) c 2 f ( n )
I was told that whilst the answer is correct, the explanation is not. Can somebody explain to my why this is the case?

Answer & Explanation

Karma Estes

Karma Estes

Beginner2022-09-06Added 11 answers

It’s not clear to me why you think that your answer does explain why the statement is false, so I don’t know just how helpful the following will be.
In order to justify your assertion that the statement is false, you need to demonstrate that it really is possible for an algorithm to be Θ ( n 2 ) and still perform more than 10 n 3 operations for at least some values of n. You’ve merely stated what it means for an algorithm to be Θ ( n 2 ) without offering any explanation of how to use this explanation to show that such a counterexample exists.
What you could have done instead is show that if T ( n ) = 10 7 + n 2 , then T(n) is Θ ( n 2 ), but clearly T ( n ) > 10 n 3 for n 100.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in High school statistics

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?