Scribd
Upload
4 views

Revision_Practice

The document contains practice problems related to algorithm complexity, including proofs for Big O and Omega notations. It demonstrates how to analyze and prove the complexities of various functions and algorithms. Additionally, it provides examples of common algorithm complexities for different operations.

Uploaded by

telacet362
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
4 views

Revision_Practice

The document contains practice problems related to algorithm complexity, including proofs for Big O and Omega notations. It demonstrates how to analyze and prove the complexities of various functions and algorithms. Additionally, it provides examples of common algorithm complexities for different operations.

Uploaded by

telacet362
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/ 5

Practice Problems

1) Prove that 5n² - 3n + 20 is in O(n²)


Solution
F(n) <= g(n)
5n² - 3n + 20 <= c n²
Removing negative term from above relation
 5n²+20n²
 25n2
Let n =1 and c = 25

5(1)² - 3(1) + 20 <= 25 (1)²

2) Prove that 2n³ - 7n + 1 = Ω(n³)


Solution:

F(n) >= cn

2n³ - 7n + 1 >= cn³


Removing negative term from above relation
 n³ + n³ - 7n + 1
 n³ + 1 > 0
 n³ - 7n > 0 , n >= 3

Let c=1 and n=3


2(3)³ - 7(3) + 1 >= (3)³
Practice for home
3) Prove that running time T(n) = n3 + 20n + 1 is O(n3 )
4) Prove that running time T(n) = n3 + 20n + 1 is not O(n2 )
5) Prove that running time T(n) = n3 + 20n is Ω(n2 )

6) Find the complexity of below recurrence:


{3T (n-1), if n>0,
T (n) = {1, otherwise
Let us solve using substitution.
 T(n) = 3T(n-1)
 3(3T(n-2))
 32T(n-2)
 33T(n-3)
 3nT(n-n)
 3nT(0)
 3n
This clearly shows that the complexity of this function is O (3n).

7)
Solution
8)

Solution
Method to characterize the execution time of algorithm

 Adding two square matrices is O(n2 )


 Searching in a dictionary is O(log n)
 Sorting a vector is O(n log n)
 Solving Towers of Hanoi is O(2n )
 Multiplying two square matrices is O(n3 )
Examples

You might also like