In Solution 1: Checking Off of Problem Solving with Algorithms and Data Structures, just beneath the ActiveCode: 1 extract (included at the bottom of this post for reference), it is stated:
each of the n characters in s1 will cause an iteration through up to n characters in the list from s2.
...which to paraphrase (less succinctly), means "each character in s1 could result in all characters in s2 being inspected".
The following sentence states:
Each of the n positions in the list will be visited once to match a character from s1.
Firstly I'm unsure which list is being referred, I think it means the variable alist
, i.e. s2
. Is this correct?
The number of visits then becomes the sum of the integers from 1 to n.
Secondly (and the real point of this post), if each item in the list (variable alist
) is inspected for each character in s1
, then why is this not simply O(n) = n^2 as per "nested loops"? If n=5, then then sum(n) = 15, where as n^2 = 25.
I'm fine with simplifying the equation for summing 1 to n integers to get n^2, but I'm confused about how sum(5) = 15, whereas O(n) = n^2.
ActiveCode: 1 Checking Off (active5)
def anagramSolution1(s1,s2):
alist = list(s2)
pos1 = 0
stillOK = True
while pos1 < len(s1) and stillOK:
pos2 = 0
found = False
while pos2 < len(alist) and not found:
if s1[pos1] == alist[pos2]:
found = True
else:
pos2 = pos2 + 1
if found:
alist[pos2] = None
else:
stillOK = False
pos1 = pos1 + 1
return stillOK
print(anagramSolution1('abcd','dcba')
Edit to add
Having written this out it struck me that perhaps dropping the (1/2)
and (1/2)n
from the formula to sum(n)
is the reason for the difference of actually summing n
, as opposed to just doing n^2
.
To be absolutely clear, I understand the formula for summing n
is n^2
when dropping the non-dominant terms. What I don't understand is why we're summing n
and not immediately and directly stating it is actually n^2
as a result of the nested loop and this sentence:
each of the n characters in s1 will cause an iteration through up to n characters in the list from s2.