Big-O and big-omega question

  • Thread starter KataKoniK
  • Start date
  • #1
168
0
Hi,

I am a bit confused here. Just say you're given code and it says to show the best-case analysis and the worst-case analysis. When you show the best-case, what should the answer be in? In big-O or big-omega? Similarly, if you show the worst-case, what should the answer be in? big-O or big-omega? Would it be correct to just show big-O for worst and best case? I am confused here about when to use both and how to use both when analysing best and worst case.
 

Answers and Replies

  • #2
0rthodontist
Science Advisor
1,230
0
In each case, choose the option that tells you something about the runtime of the elements of some arbitrary sequence of inputs. Let these runtimes be given by the function A(n).

Now let B(n) denote the runtimes of the elements of a similar sequence of worst-case inputs. You know that A(n) <= B(n). Now do you know anything additional about the long-term behavior of A(n) if you know
a. [tex]B(n) \in O(f(n))[/tex]?
b. [tex]B(n) \in \Omega(f(n))[/tex]?

Choose the one that gives you more information about A(n). And take a similar argument for describing the best case inputs.
 

Related Threads on Big-O and big-omega question

  • Last Post
Replies
0
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
6
Views
4K
Replies
1
Views
577
  • Last Post
Replies
1
Views
1K
Replies
0
Views
2K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
4
Views
795
  • Last Post
Replies
7
Views
6K
Top