Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

  • Index
  •  » Help Me !
  •  » Special Functions and Computational Complexity

#1 2013-04-02 10:24:37

rhymin
Member

Offline

Special Functions and Computational Complexity

I'm working out of a friend's textbook to try and prepare myself for a class I'll be taking in a month or so. I was wondering if someone could give me the answers to these problems so I have a better understanding of how to solve them?


1) How do you figure the degree of the table?

Let A_i, 1 ≤ i ≤ 5, be the domains for a table D ⊆ A_1 x A_2 x A_3 x A_4 x A_5, where A_1 = {U, V, W, X, Y, Z} (used as code names for different cereals in a test), and A_2 = A_3= A_4 = A_5 = Z^+.

Table D:

Code Name of Cereal / Grams of Sugar per 1-oz Serving / % of RDA^a of Vitamin A per 1-oz Serving / % of RDA Vitamin C per 1-oz Serving / % of RDA of Protein per 1-oz Serving
U    1    25    25    6
V    7    25    2    4
W    12    25    2    4
X    0    60    40    20
Y    3    25    40    10
Z    2    25    40    10



2) How do you determine the best "big-Oh" form?

Use the results of Table 1 to determine the best big-Oh form for the following function f: Z^+→ R.
f(n) = 3n + 7

Table 1 (I'm not sure how to write tables so I used the dash (-----):


Big-Oh Form ------------------------ Name
O(1) --------------------------------- Constant
O(log_2 n) -------------------------- Logarithmic
O(n) --------------------------------- Linear
O(n log_2 n) ------------------------ n log_2 n
O(n^2) ------------------------------ Quadratic
O(n^3) ------------------------------ Cubic
O(n^m), m = 0, 1, 2, 3,... ------- Polynomial
O(c^n), c > 1 ----------------------- Exponential

  • Index
  •  » Help Me !
  •  » Special Functions and Computational Complexity

Board footer

Powered by FluxBB