in Flutter there are two functions :
in the docs they say that: findAncestorWidgetOfExactType is relatively expensive (O(N) in the depth of the tree).
and dependOnInheritedWidgetOfExactType is O(1) with a small constant factor.
anyone can explain why ? why the first one is more expensive than the other ?
Thanks
To answer the question and understand why there is a difference in time complexity between the two methods, we first need to clarify two things:
1- What is Linear Searching ?
Linear search (known as sequential search) is an algorithm for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
And in short, O(1) means that it takes a constant time, (for example 10 nanoseconds).
on the other hand O(N) means it takes an amount of time linear with the size of the set, so a set twice the size will take twice the time. You probably don't want to put a million objects into one of these.
hence the hint in the docs of ( findAncestorWidgetOfExactType )
"Only call this method if the distance from this widget to the desired ancestor is known to be small and bounded."
2- What is the Generic 'Type' each method searches for and Where ?
with these in mind we can answer the question .. so Why ?
Because the findAncestorWidgetOfExactType method is searching in all the widget tree ( cause they are all of type Widget by default )
and this is done by linear searching up the widgets tree thus comes => O(N).
This part is updated thanks to Mabsten answer
on the other hand dependOnInheritedWidgetOfExactType
searches Not in the widget tree but instead in a map that comes with every Element containing all ancestor InheritedWidgets, indexed by their type.
So 'dependOn' - directly - fetches the right inherited widget from this map that's why it is O(1).