Algorithms Analysis & Design - Lecture 3

Introduction to the Design and Analysis of Algorithms

1. Algorithms
By Mohamed Gamal
© Mohamed Gamal 2024

3. –L'Hôpital's rule (or sometimes spelled L'Hospital's rule) is a method used to find
limits of indeterminate forms in calculus.
–When you apply this rule (possibly multiple times), it can simplify an indeterminate
limit into a form that’s easier to evaluate by direct substitution.
–The rule is named after Guillaume de l'Hôpital, a French mathematician from the
17th century.
–However, the theorem was originally introduced to him by Johann Bernoulli, a Swiss
mathematician, in 1694.
L'Hôpital's rule
Guillaume de l'HôpitalJohann Bernoulli

5. –In mathematics, computer science, and engineering, it's often crucial to compare
how quickly different functions grow as their input � becomes large.
–Exponential functions are significant in these comparisons due to their rapid growth,
while logarithmic functions are notable for their very slow growth.
–Exponential functions, such as 2
??????
and �
??????
, grow much faster than polynomials or
rational functions as � increases.
–For example, 2
??????
grows much faster than �
2
as � becomes large. In fact, 2
??????
and �
??????

grow faster than any polynomial function, even those with very high powers like
�
1,000,000
.
–On the other hand, logarithmic functions like �=log
2� and �=ln� grow much
more slowly compared to any positive power of � as � increases.
Relative Rates of Growth

6. Fig. Comparing relative rates of growth.

7. Comparing Orders of Growth (Using Limits)
(Stirling's formula)
(L'Hôpital's rule)

11. Orders of growth from the lowest to highest.
O1 Best
Olog??????
O2log??????
O(??????)
O??????log??????
O(??????
2
)
O(??????
3
)
O(2
??????
)
O(??????!) Worst

12. Question 1

13. a) n(n+1) ≈ ??????
2
has the same order of growth as 2000??????
2
b) 100??????
2
≈ ??????
2
has a lower order of growth than 0.01??????
3
≈ ??????
3
c) log
2??????, ln?????? = log
????????????=lg ??????, log??????=log
10??????
– All logarithmic functions have the same order of growth
d) log
2
2
?????? = log
2?????? log
2?????? = (log
2??????)
2

log
2??????
2
= 2 log
2??????
(log
2??????)
2
has a higher order of growth than log
2??????
e) 2
??????−1
=
2
??????
2
=
1
2
2
??????
has the same order of growth as 2
??????
f) (??????−1)! Has a lower order of growth than ??????! = ?????? (??????−1)!

14. Question 2

15. 1) 5 lg(??????+100)
10
= 50 lg(n + 100) ∈ O (log ??????)
2) ln
2
?????? ∈ O (log
2
??????)
3)
3
?????? ∈ O (??????
Τ
1
3)
4) 0.001??????
4
+ 3??????
3
+ 1 ∈ O ( ??????
4
)
5) 3
??????
6) 2
2??????
= (2
2
)
??????
= 4
??????
7) (??????−2)! ∈ O (??????!)

17. Useful summation formulas and rules
We use Summation to calculate
for loops run time.

18. Example: estimate the run time of the following.
for (i=0; i<n; i++)
print(i)
෍
&#3627408470;=??????&#3627408450;??????????????????
??????&#3627408451;&#3627408451;????????????
1 =
&#3627408456;&#3627408451;&#3627408451;&#3627408440;&#3627408453;−??????&#3627408450;??????&#3627408440;&#3627408453;+1
2
×(&#3627408441;??????&#3627408453;&#3627408454;&#3627408455;+????????????&#3627408454;&#3627408455;)
෍
&#3627408470;=0
??????−1
1=
??????−1−0+1
2
×(1+1)=??????∈ O(??????)

19. Example: estimate the run time of the following algorithm.
for (i=1; i<n; i++)
for (j=1; j<n; j++)
print(i)
෍
&#3627408470;=1
??????−1
෍
&#3627408471;=1
??????−1
1=෍
&#3627408470;=1
??????−1
??????−1−1+1
2
×1+1=෍
&#3627408470;=1
??????−1
(??????−1)=
??????−1−1+1
2
×??????−1+??????−1=??????−1
2
෍
&#3627408470;=??????&#3627408450;??????????????????
??????&#3627408451;&#3627408451;????????????
1 =
&#3627408456;&#3627408451;&#3627408451;&#3627408440;&#3627408453;−??????&#3627408450;??????&#3627408440;&#3627408453;+1
2
×(&#3627408441;??????&#3627408453;&#3627408454;&#3627408455;+????????????&#3627408454;&#3627408455;)
∈ O(??????
2
)

20. Example: estimate the run time of the following.
for (i=n; i<=2n; i++)
for (j=1; j<=i; j++)
print(i)
෍
&#3627408470;=??????&#3627408450;??????????????????
??????&#3627408451;&#3627408451;????????????
1 =
&#3627408456;&#3627408451;&#3627408451;&#3627408440;&#3627408453;−??????&#3627408450;??????&#3627408440;&#3627408453;+1
2
×(&#3627408441;??????&#3627408453;&#3627408454;&#3627408455;+????????????&#3627408454;&#3627408455;)
෍
&#3627408470;=??????
2??????
෍
&#3627408471;=1
&#3627408470;
1=෍
&#3627408470;=??????
2??????
??????−1+1
2
×1+1=෍
&#3627408470;=??????
2??????
??????=
2??????−??????+1
2
×??????+2??????=
3
2
??????
2
+??????
∈ O(??????
2
)

21. Example: Estimate Algorithm run time.
for (i=1; i<n; i++)
for (j=1; j<n; j++)
for (k=1; j<n; k++)
print(i)

෍
&#3627408470;=??????&#3627408450;??????????????????
??????&#3627408451;&#3627408451;????????????
1 =
&#3627408456;&#3627408451;&#3627408451;&#3627408440;&#3627408453;−??????&#3627408450;??????&#3627408440;&#3627408453;+1
2
×(&#3627408441;??????&#3627408453;&#3627408454;&#3627408455;+????????????&#3627408454;&#3627408455;)
෍
&#3627408470;=1
??????−1
෍
&#3627408471;=1
??????−1
෍
&#3627408472;=1
??????−1
1=෍
&#3627408470;=1
??????−1
෍
&#3627408471;=1
??????−1
??????−1−1+1
2
×1+1=෍
&#3627408470;=1
??????−1
෍
&#3627408471;=1
??????−1
??????−1=෍
&#3627408470;=1
??????−1
??????−1−1+1
2
×??????−1+??????−1
=෍
&#3627408470;=1
??????−1
??????−1
2
=
??????−1−1+1
2
×??????−1
2
+??????−1
2
=??????−1
3
∈ O(??????
3
)

22. Example:
i = 1
while i <= n
begin
print(i)
i = i + 2
end
We use trace to calculate while loops run time.
Let n = 5
i = 1, 3, 5
Let n = 8
i = 1, 3, 5, 7
Let n = 10
i = 1, 3, 5, 7, 9
3 times
4 times
5 times
&#3627408467;??????=
??????
2
or &#3627408467;??????=
??????+1
2
∈ O(??????)

23. Example:
i = n
while i >= 1
begin
for j = 1 to n
print(i, j)
i = i/2
end
Let n = 4
i = 4, 2, 1
Let n = 8
i = 8, 4, 2, 1
Let n = 16
i = 16, 8, 4, 2, 1
3 times
4 times
5 times
??????
&#3627408467;??????=log
2??????+1 × ??????
while loop for loop
=?????? log
2??????+??????∈ O(??????log
2??????)
log
2??????+1

24. Operation: doesn’t depend on input size. O(1)
for/while Loops:
++ increment: i = i + 1, i = i + 2, i = i + 5
– – decrement: i = i - 1, i = i – 3, i = i – 10
multiplication: i = i * 2, i = i * 5
division: i = i / 2, i = i / 9
Summary
O(??????)
O(log??????)

25. Conditions (if-else statements): maximum time of the conditions.
Example:
if (n > 3) {
print(n)
} else {
for(i = 1; i <= n; i*=2)
print(n)
}
Maximum(1,log??????) = O(log ??????)
O(1)
O(log??????)

26. Thank You!