[go: up one dir, main page]
Scribd
Upload
10 views1 page

Tutorial 1 - Time Complexity Functions

Uploaded by

stl2688divyansh10
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
10 views1 page

Tutorial 1 - Time Complexity Functions

Uploaded by

stl2688divyansh10
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
You are on page 1/ 1

Jaypee University of Engineering and Technology

18B11CI311 – Data Structures


B.Tech -3rd Semester
Tutorial – 1 (Time Complexity)

1.Find the exact step counts (growth function) and time complexity for following algorithms -

2. Show that following statements are correct:


i. 4n+100=O(n) ii. 500n3 +6n+6=O(n3)
iii. n3 ≠ O(n2) iv. 5n2-6n= O(n2)
v. n! = O(nn) vi. 2n22n +nlogn= O(n22n)
𝑛
3 2 2 2
vii. 3n +4n = Ω(n ) viii. ∑ 𝑖 =θ(n3)
𝑖=0

3. Compare the two functions n2 and 2n/4 for various values of n. Determine when the second becomes
larger than the first.

4. Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2,
f3 and f4?
f1(n) = 2^n, f2(n) = n^(3/2), f3(n) = nLogn, f4(n) = n^(Logn)

You might also like