KEMBAR78
A Look at Simple Exercises | PDF
Scribd
Upload
7 views11 pages

A Look at Simple Exercises

The document contains exercises focused on analyzing algorithms, including identifying input size metrics and basic operations for computing sums and finding maximum elements. It also compares the order of growth of various functions and assesses assertions related to Big O notation. Solutions are provided for each exercise, confirming the relationships between the functions and their growth rates.

Uploaded by

patelsamir0950
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
7 views11 pages

A Look at Simple Exercises

The document contains exercises focused on analyzing algorithms, including identifying input size metrics and basic operations for computing sums and finding maximum elements. It also compares the order of growth of various functions and assesses assertions related to Big O notation. Solutions are provided for each exercise, confirming the relationships between the functions and their growth rates.

Uploaded by

patelsamir0950
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/ 11

A look at Simple exercises

Advanced Algorithms
Exercise 1

 For each of the following algorithms, indicate


 (i) a natural size metric for its inputs;
 (ii) its basic operation;
 a). computing the sum of n numbers
 b). finding the largest element in a list of n
numbers
Hint:

 The questions are indeed as straightforward


as they appear, though some of them may
have alternative answers. Also, keep in mind
the caveat about measuring an integer’s size.
Solution

 The answers are as follows.


a). (i) n; (ii) addition of two numbers;

b). (i) n; (ii) comparison of two numbers ;


Exercise 2

 Indicate whether the first function of each of


the following pairs has a smaller, same, or
larger order of growth (to within a constant
multiple) than the second function.
a). n(n + 1) and 2000𝑛2 .
b). 100 𝑛2 and 0.01 𝑛3 .
c). log2 𝑛 and ln 𝑛.
Hint

 If necessary, simplify the functions in question


to single out terms defining their orders of
growth to within a constant multiple.
Solution
 a). n(n + 1) ≈ 𝑛2 has the same order of growth
(quadratic) as 2000 𝑛2 to within a constant multiple.

 b). 100 𝑛2 (quadratic) has a lower order of growth


than 0.01n3 (cubic).

 c). Since changing a logarithm’s base can be done


by the formula
log 𝑎 𝑛 = log 𝑎 𝑏 log 𝑏 𝑛,
all logarithmic functions have the same order of
growth to within a constant multiple.
Exercise 3

 Use the informal definitions of O, Θ, and Ω to


determine whether the following assertions
are true or false.

a) n(n + 1)/2 ∈ O(𝑛3 )


b) n(n + 1)/2 ∈ O(𝑛2 )
Hint

 Establish the order of growth of n(n+1)/2 first


and then use the informal definitions of O, Θ,
and Ω.
Def order of growth
A way of comparing functions that ignores
constant factors and small input sizes
 O(g(n)): class of functions f(n) that grow no
faster than g(n)
 Θ(g(n)): class of functions f(n) that grow at
same rate as g(n)
 Ω(g(n)): class of functions f(n) that grow at least
as fast as g(n)
Solution

 n(n + 1)/2 ≈ 𝑛2 /2 is quadratic. Therefore

 a). n(n + 1)/2 ∈ O(𝑛3 ) is true.


 b). n(n + 1)/2 ∈ O(𝑛2 ) is true.

You might also like