Arrays - 2D Arrays
Suppose we have data of daily rainfall for a year. Find the maximum monthly average rainfall over a year.
- Lets assume that there are $d$ days in a month and $m$ months in a year.
We could store rainfall data in a 2D array of size $m\times d$:
| 1 | 2 | … | $d$ | |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| … | ||||
| $m$ |
rainfall[i][j] stores rainfall of month $i$ and day $j$.
You can split the problem into the following questions:
- What is the average rainfall of month $i$?
- What is the maximum average?
Average of Month $i$
j = 1
sum = 0
while j <= d do
begin
sum += rainfall[i][j] # ask for i
j++
end
average = sum / d
This is the nested portion of the loop. $i$ should be incremented outside.
Maximum of the Averages
m = 0
i = i
while i <= m do
begin
sum = 0
for j = 1 to d do
sum += rainfall[i][j]
average = sum / d
if average > m then
m = average
i++
end
output m
Time Complexity
The nested portion has a time complexity of $O(d)$. This is repeated $m$ times giving an overall time complexity of:
\[O(m\times d)\]