Page 30 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 2: Data Structure Operations and Algorithms Complexity

2.3.4 More Properties Notes

The first four properties listed above for big O are also true for Omega and Theta.
Replace O with Ω and “largest” with “smallest” in the fifth property for big O and it
remains true.
f(n) = Ω(g(n)) is true if limn->infinityg(n)/f(n) is a constant.

f(n) = Θ(g(n)) is true if limn->infinityf(n)/g(n) is a non-zero constant.
nk = O((1+ε) n)) for any positive k and ε. That is, any polynomial is bound from above by
any exponential. So any algorithm that runs in polynomial time is (eventually, for large
enough value of n) preferable to any algorithm that runs in exponential time.

(log n)ε = O(n k) for any positive k and ε. That means a logarithm to any power grows
more slowly than a polynomial (even things like square root, 100th root, etc.)

!
Caution An algorithm that runs in logarithmic time is (eventually) preferable to an
algorithm that runs in polynomial (or indeed exponential, from above) time.

Self Assessment

Fill in the blanks:
8. “.........................” refers to a way of rating the efficiency of an algorithm.
9. Every function f(n) bounded above by some constant multiple g(n) for all values of n
greater than a certain value is ..........................
10. A function “.........................” means that the algorithm requires the same fixed number of
steps regardless of the size of the task.
11. A function “.........................” means that the algorithm requires a number of steps
proportional to the size of the task.
12. In case of “.........................” function, the number of operations is proportional to the size of
the task squared.
13. “.........................” time includes more advanced sorting algorithms.

14. Big O is ........................., that is, if f(n) = O(g(n)) and g(n) is O(h(n)), then f(n) = O(h(n)).

Case Study Algorithm Analysis

ere we show how to use the big-Oh notation to analyze three algorithms that
solve the same problem but have different running times. The problem we focus
Hon is one that is reportedly often used as a job interview question by major
software and Internet companies—the maximum subarray problem. In this problem, we
are given an array of positive and negative integers and asked to find the subarray whose
elements have the largest sum. That is, given A = [a , a , . . . , a ], find the indices j and k that
1 2 n
maximize the sum
k
s , j k = a j + a j +1 +... a k = ∑ a i
+
= ij
Contd...

LOVELY PROFESSIONAL UNIVERSITY 23