Big O Notation, Algorithm Complexity Analysis Homework Solution

This assignment provides solutions to several problems related to Big O notation and algorithm complexity analysis. It begins by determining the order of x^2ln(x), demonstrating that it is O(x^3). The assignment then explores the conditions under which |2x + 3| ≤ C|x^2| holds true for x > k, finding suitable values for C and k. It also proves that x^3 is not O(x^2) by demonstrating that the constant C cannot be independent of x. The complexity of the expression (1 + √x)^2 is determined to be O(x). Finally, the assignment analyzes the Big O notation of two complex polynomial expressions, simplifying them to O(6x) and O(x^4*(1.2x)), respectively. This solved assignment can be found on Desklib, a platform offering study tools and resources for students.

Q1)
The expression we have is x2ln(x)
Using the rule that express
O[f1(x) * f2(x)]= O( f1(x)) * O( f2(x))
Therefore;
O f1(x) = x2 = O(x2)
F2 = ln(x) = O(x)
Hence;
O(x2ln(x)) = O(x2) * O(x) = O(x3)
Thus;
X2ln(x) is order of x3
Q2)
|f ( x) | ≤ C | g ( x ) | for all x > k
| 2 x + 3 | ≤ C | x^2 | for all x > k
a) when C = 1
Then;
| 2 x + 3 | ≤ C | x2 |
| 2 x + 3 | ≤ | x2 |
| 2 x + 3 | ≤ x2
This is true for all x ≥3
Therefore;
k = 3

b)
| 2 x + 3 | ≤ C | x2 | for x > 2
|2*2 + 3| <= 22C
7 ≤ 4C
C≥ 7/4
Therefore;
C =7/4
Q3)
To prove that
X3 ≠ O(x2)
By definition of big-O
f(x) = O(g(x))
if ) ≤ f (n) ≤ cg(n) for all n ≥ k and 0 ≤ c <n
Therefore;
f(n) must be less than C*g(n) where C must not be equal to n and c must be an integer
Hence;
f(n) = x3
g(n) = x2
To prove that x3
≤ C∗x2

The value of C∗x2 can not be greater than x3 unless C≥ x, which in this case can not be
truebecause C is not a polynomial
Hence;
X3 ≠ O(x2)
Q4) expanding the expression (1 + √ x)2
Then we will have 1+x+2x1/2
From this expression we can see that highest power of x is 1, therefore the smallest value of n
can be 1.
Therefore, the complexity will be O(x) .
Hence the value of n=1
Q5)
a) f(x) = (x4 + xlnx6)(5x + x6) + (x2 + 3x)(x2 + 2x)
= (x4 + 6xlnx)(5x + x6) + (x2 + 3x)(x2 + 2x)
= x4*5x + 6xlnx * 5x + x10 + 6x7*lnx + x4 + 2x*x2 + 3x*x2 + 6x
Then
lim
x→ ∞
f (x)
x4∗5x =+∞
And
lim
x→ ∞
f ( x)
6x =1
f(x) = O(6x)
b) f(x) = (x4 + xlnx6)(1.1x + 1.2x) + (x2 + 1.2x)(x3 + 0.92x)
= x4(1.1x) + x4(1.2x) + 6xlnx * 1.1x + 6xlnx * 1.2x + x6 + 0.92x *x2 + (1.2x)*(0.92x)
Then

lim
x→ ∞
f (x)
x4∗1.2x =1
Therefore;
f(x) = O(x4*(1.2x))