2

Just attended my first Data Structure Algorithm class and I do not understand it at all. One question given to me was:

Arrange the following functions into increasing order; that is, () should come before () in your list if and only if () is (()).

3^2n , 5n lg n + 20n , n^0 , 2^lg n , 16 ^lg n

So what should I do? Substitute n as 1 and work each function out before sorting them?

A. Sarid
  • 3,916
  • 2
  • 31
  • 56
Euru
  • 55
  • 3
  • 4
    Do you know what (()) means? That's really the important part here. – jwodder Jul 10 '17 at 02:33
  • 3
    https://math.stackexchange.com/questions/955186/arrange-the-following-growth-rates-in-increasing-order-o-n-log-n2-o-35 – Eugene S Jul 10 '17 at 02:34
  • Hint: what is O(g(n)) if g(n) = 3^(2n)? That is, what is O(3^(2n))? What about O(5n lg n + 20n)? What about O(n^0)? – Seth Difley Jul 10 '17 at 02:44
  • 1
    @jwodder To my understanding, it means that f(n) ≤ g(n) – Euru Jul 10 '17 at 02:45
  • 1
    @EugeneS Thanks for the link! Giving it a good read through. – Euru Jul 10 '17 at 02:46
  • @SethDifley hmm I still do not understand the Big-O notation to answer you.. – Euru Jul 10 '17 at 02:57
  • I'm wondering about the question, why is it comparing f(n) to O(g(n))? Seems the ordering is to based on the list of expressions for n sufficiently large enough that the ordering of the functions no longer changes for greater values of n. – rcgldr Jul 10 '17 at 05:12
  • 1
    Right I think i figured it out. Can someone help me take a look? n^0 , 2^lg n, 16^lg n , 5n lg n + 20n , 3^2n – Euru Jul 10 '17 at 06:57
  • Possible duplicate of [What is a plain English explanation of "Big O" notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) – xenteros Jul 10 '17 at 07:31

1 Answers1

4

First, I'd suggest you to go and read about the big-O notation. Then, if you'll take a look at the link @EugeneS gave you in the comment you'll notice this:

O(n^n) > O(n!) > O(α^n) > O(n^α) > O(log(n)) > O(1)

So lets break things down a bit:

1. O(3^2n) = O(α^n)
2. O(5nlogn+20n) = O(nlogn)
3. O(n^0) = O(1)
4. O(2^logn) = O(α^logn)
5. O(16^logn) = O(α^logn)

Now you said

() should come before () in your list if and only if () is (()).

Can you arrange them now? According to what you understood on big-O and the list above. The right arrangement would be

O(α^n) > O(α^logn) > O(α^logn) > O(nlogn) > O(1)

1 > 5 > 4 > 2 > 3

Note to yourself: This is really the basics and it is very important, so make sure you understand this before moving on with your course material.

A. Sarid
  • 3,916
  • 2
  • 31
  • 56