Homework SourseProve that 1 log 1 2 log 2 3 log 3 n log n n2 log n Q2
Prove that: (1 log 1 + 2 log 2 + 3 log 3 + … + n log n) = (n2 log (n))
Q2, 3, 4 (5 points each): What is the time complexity of this algorithm, in terms of n?
[Just as an FYI, Sum += y is a short form notation for Sum = Sum + y.]
A-
j = 1
while (j < n) {
k = n/2
while (k < n) {
Sum += a[j]*b[k]
k = k * k
}
j++
}
b-
For (int j = 1 to n) {
For (int k = j to n) {
x = k
While (x < n) {
Sum += a[j]*b[k]*c[x]
If (x % 3 == 0) {
x = n + 1
}
x = x + 1
}
}
}
c-
For (int j = 1 to n) {
k = j
while (k < n) {
Sum += a[k]*b[k]
k += log n
}
}
Solution
The time complexity of this algorithm
A)
j = 1
while (j < n) {
k = n/2
while (k < n) {
Sum += a[j]*b[k]
k = k * k
}
j++
}
Answer: O(n2)
The time complexity of this algorithm = O(n2)
b)
For (int j = 1 to n) {
For (int k = j to n) {
x = k
While (x < n) {
Sum += a[j]*b[k]*c[x]
If (x % 3 == 0) {
x = n + 1
}
x = x + 1
}
}
}
Ans : O(1)
c)
For (int j = 1 to n) {
k = j
while (k < n) {
Sum += a[k]*b[k]
k += log n
}
}
Answer: O(n).
The base of the log n might be something else, but the the time complexity of this algorithm is = O(n)
