Skip to main content
Computer Science

Return to Question

edited tags
Link
Raphael
Raphael
  • 73.4k
  • 31
  • 184
  • 406
deleted 268 characters in body
Source Link
John
John
  • 3
  • 3

I am currently learning landau notations and am stuck on the following True/False question.

Let A and B be two different algorithms for solving a given computational problem. Assume that the worst-case running time of A is Θ(n) and the worst-case running time of B is Θ(n log n). Hence, one can always find an input to the problem such that A runs faster than B on this input. True or false? Why?

Quession

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough. But i am not sure if my reasoning is correct and if i get the big picture here.

I am currently learning landau notations and am stuck on the following True/False question.

Let A and B be two different algorithms for solving a given computational problem. Assume that the worst-case running time of A is Θ(n) and the worst-case running time of B is Θ(n log n). Hence, one can always find an input to the problem such that A runs faster than B on this input. True or false? Why?

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough. But i am not sure if my reasoning is correct and if i get the big picture here.

I am currently learning landau notations and am stuck on the following True/False question.

Quession

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough. But i am not sure if my reasoning is correct and if i get the big picture here.

Source Link
John
John
  • 3
  • 3

Out of these two algorithms. Is there always an input where A is faster then B? (Big theta notation)

I am currently learning landau notations and am stuck on the following True/False question.

Let A and B be two different algorithms for solving a given computational problem. Assume that the worst-case running time of A is Θ(n) and the worst-case running time of B is Θ(n log n). Hence, one can always find an input to the problem such that A runs faster than B on this input. True or false? Why?

What seems a little confusing to me is the use of big-theta notation to describe worst-case run-time. What is the difference in saying "worst-case run-time Θ(n log n)" or simply "run-time O(n log n)"? Giving the worst case a tight limit seems a lot like simply giving an upper bound to the run-time.

If I go by that reasoning my guess would be that the statement is true. As an O(n) algorithm will be faster than an O(n log n) as n grows large enough. But i am not sure if my reasoning is correct and if i get the big picture here.