I'm in the middle of reading Effective Go, and there is a piece of code which I think is O(n)
complexity yet it is O(n²)
. Why is this for range
loop considered to be O(n²)
?
It is found here (under #interfaces)
type Sequence []int
...
func (s Sequence) String() string {
...
for i, elem := range s { // Loop is O(N²); will fix that in next example.
if i > 0 {
str += " "
}
str += fmt.Sprint(elem)
}
...
}
The reason I think it is O(n)
is because there is only one iteration over s
, and the if
statement and fmt.Sprint
should not be in O(n)
complexity.