Scribd
Upload
16 views3 pages

Solution

The document discusses time complexity analysis for various algorithms, providing explanations for complexities such as O(n log n), Θ(log n), and O(n^k). It includes examples demonstrating how certain variables behave in relation to n, and references external links for further reading. Additionally, it confirms the transitive properties of Θ and O notations.

Uploaded by

vk640
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views3 pages

Solution

The document discusses time complexity analysis for various algorithms, providing explanations for complexities such as O(n log n), Θ(log n), and O(n^k). It includes examples demonstrating how certain variables behave in relation to n, and references external links for further reading. Additionally, it confirms the transitive properties of Θ and O notations.

Uploaded by

vk640
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Ques.

3
(c) O(n*logn)
Explaination:-
If you notice, j keeps doubling till it is less than or equal to n. Several times, we can double a
number till it is less than n would be log(n).
Let’s take the examples here.
for n = 16, j = 2, 4, 8, 16
for n = 32, j = 2, 4, 8, 16, 32
So, j would run for O(log n) steps.
i runs for n/2 steps.
So, total steps = O(n/ 2 * log (n)) = O(n*logn)

(d) Θ (logn)
Explaination:- Visit this link
https://www.geeksforgeeks.org/interesting-time-complexity-question/

(e) O(n*logn)
Explaination:- The outer loop will run for n/2 times and for each iteration of the outer loop, inner
loop will run log2n times.

(f) O(nk)
Explaination: Visit this link
https://www.geeksforgeeks.org/time-complexity-of-loop-with-powers/

Ques. 5
1. True. Θ is transitive
2. True. O is transitive, and h(n) = Ω(f(n)) is the same as f(n) = O(h(n))

Ques.8 Θ(3n2 + 2)
Explaination: Visit this link
https://www.geeksforgeeks.org/practice-set-recurrence-relations/

You might also like