Page 34 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES
P. 34
Unit 2: Data Structure Operations and Algorithms Complexity
Notes
Output: The subarray summation value such that A[j] + · · · + A[k] is maximized.
M ← 0 // the initial prex maximum
0
for t ← 1 to n do
M ← max{0, M + A[t]}
t t – 1
m ← 0 // the maximum found so far
for t ← 1 to n do
m ← max{m, M }
t
return m
Analyzing the MaxsubFastest Algorithm
The MaxsubFastest algorithm consists of two loops, which each iterate exactly n times and
take O(1) time in each iteration. Thus, the total running time of the MaxsubFastest algorithm
is O(n). Incidentally, in addition to using the accumulator pattern, to calculate the M and
t
m variables based on previous values of these variables, it also can be viewed as a simple
application of the dynamic programming technique. Given all these positive aspects of
this algorithm, even though we can’t guarantee that a prospective employee will get a job
offer by describing the MaxsubFastest algorithm when asked about the maximum subarray
problem, we can at least guarantee that this is the way to nail this question.
Questions
1. Illustrate the use of big-Oh notation to analyze algorithm.
2. Discuss MaxsubFaster algorithm.
Source: http://www.ics.uci.edu/~goodrich/teach/cs161/notes/MaxSubarray.pdf
2.4 Summary
We can use various operations on data structures such as traversing, insertion, deletion,
sorting, merging, etc.
An algorithm is a clearly specified set of simple instructions to be followed to solve a
problem.
The most important resource to analyze is generally the running time. Several factors
affect the running time of a program.
The complexity of an algorithm is a function describing the efficiency of the algorithm in
terms of the amount of data the algorithm must process.
Time complexity is a function describing the amount of time an algorithm takes in terms
of the amount of input to the algorithm.
Space complexity is a function describing the amount of memory (space) an algorithm
takes in terms of the amount of input to the algorithm.
The difference between space complexity and time complexity is that space can be reused.
Space complexity is not affected by determinism or nondeterminism.
“Big O” refers to a way of rating the efficiency of an algorithm. It is only a rough estimate
of the actual running time of the algorithm, but it will give you an idea of the performance
relative to the size of the input data.
LOVELY PROFESSIONAL UNIVERSITY 27
