Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

• 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