Question

*True or False...Provide your reasons*

- If f(n) =o(g(n)), then f(n)=O(g(n))
- If f(n) =O(g(n)), then f(n) ≤ g(n)

3. If 1<a=O(n^{a}), then
f(n)=O(n^{b})

4. A and B are two sorting algorithms. If A is O(n^{2})
and B is O(n), then for an input of X integers, B can sort it
faster than A.

Answer #1

Ans

False

f(n) = o(g(n)) does not imply f(n)= O(g(n))

It means f(n)<c.g(n) but does not mean f(n)<=c.g(n)

False

f(n) = O(g(n)) means f(n)<=c.g(n) where c>0 but it does not mean c=1. Hence f(n) <=g(n) is not inference .

3) False

1<a=O(n^{a}) means
1<a<=c.n^{a}

then f(n)<=c.n^{b}

^{we can't say anything about f(n) and b.}

4) True

B is O(n) while A is O(n²). So, number of operation in B less than that of A for n>0. So, B execute faster.

If any doubt ask in the comments.

True for false
An arraylist is a statically allocated data structure
(true/false)
Program efficiency is best calculated by counting the execution
times of programs(true/false)
There are algorithms that are cheaper, hence faster than
O(N2) when sorting a highly unsorted
list(true/false)
Java handles cleanup of unreferenced objects in memory
automatically (true/false)

Determine wether the statements are true or false
1. Suppose we have f(n) = nlgn , g(n) = 5n
, then f(n) = O(g(n)).
2. Suppose we have f(n) = nn/4 , g(n) =
n1/2lg4n , then f(n) = O(g(n)).
3. No comparison-based sorting algorithm can do better than
Ω(n log n) in the worst-case
4. Quicksort running time does not depend on random
shuffling.

Assume that f(n) = O(g(n)). Can g(n)
= O(f(n))? Are there cases where g(n) is
not O(f(n))? Prove your answers (give examples
for the possible cases as part of your proofs, and argue the result
is true for your example).

1. a True or False? If ∫ [ f ( x ) ⋅ g ( x ) ] d x = [ ∫ f ( x )
d x ] ⋅ [ ∫ g ( x ) d x ]. Justify your answer.
B. Find ∫ 0 π 4 sec 2 θ tan 2 θ + 1 d θ
C. Show that ∫ 0 π 2 sin 2 x d x = ∫ 0 π 2 cos...

Understand the complexity of algorithms.
Find the c and N for the function g
so that f(n) = O(g(n)).
1) f(n) = 4n2 +
3n + 6, g(n) =
n2
2) f(n) = 3n2 +
2n + 8, g(n) =
n3
3) f(n) = n2 +
4n, g(n) = n2
4) f(n) = 1000 n + 2000,
g(n) = n
5) f(n) = 1000 n + 2000,
g(n) = n2
6) f(n) = 1000 n + 2000,
g(n) = n3...

True or False? No reasons needed.
(e) Suppose β and γ are bases of F n and F m, respectively.
Every m × n matrix A is equal to [T] γ β for some linear
transformation T: F n → F m.
(f) Recall that P(R) is the vector space of all polynomials with
coefficients in R. If a linear transformation T: P(R) → P(R) is
one-to-one, then T is also onto.
(g) The vector spaces R 5 and P4(R)...

i) F o r t h e f o l l o w I n g f i n d t h e ( c o m p. E x
p.) f o u r I e r s e r i e s f o r x( t )
I I ) D r a w t h e am p &. P h a s e s p e c t r a
I I I ) T...

Determine if the following statements are true or false.
In either case, provide a formal proof using the definitions of
the big-O, big-Omega, and big-Theta notations. For instance, to
formally prove that f (n) ∈ O(g(n)) or f (n) ∉ O(g(n)), we need to
demonstrate the existence of a constant c and a sufficient large n0
such that f (n) ≤ c g(n) for all n ≥ n0, or showing that there are
no such values.
a) [1 mark] 10000n2...

5. Determine whether the following statements are TRUE or FALSE.
If the statement is TRUE, then explain your reasoning. If the
statement is FALSE, then provide a counter-example. a) The
amplitude of f(x)=−2cos(X- π/2) is -2 b) The period of
g(x)=3tan(π/4 – 3x/4) is 4π/3.
. c) If limx→a f (x) does not
exist, and limx→a g(x) does not exist, then limx→a (f (x) + g(x))
does not exist. Hint: Perhaps consider the case where f and g are
piece-wise...

(6) Label each of the following statements as True or
False. Provide justification
for your response.
(b) True/False The scalar λ is an eigenvalue of a
square matrix A if and
only if the equation (A − λIn)x = 0 has a nontrivial
solution.
(c) True/False If λ is an eigenvalue of a matrix A, then there is
only
one nonzero vector v with Av = λv.
(d) True/False The eigenspace of an eigenvalue of an n × n matrix...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 6 minutes ago

asked 7 minutes ago

asked 28 minutes ago

asked 29 minutes ago

asked 50 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago