# Special Functions and Computational Complexity

• April 1st, 2013, 06:23 PM
rhym1n
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? I'm going to be taking programming class too (Java and a couple others) and figured some of you guys are pretty good at this stuff.

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