Why findAncestorWidgetOfExactType is O(N) and dependOnInheritedWidgetOfExactType is O(1)

Question

in Flutter there are two functions :

• findAncestorWidgetOfExactType
• dependOnInheritedWidgetOfExactType

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

Acinaciform

Answer 1

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 ?

• dependOnInheritedWidgetOfExactType< T extends InheritedWidget >
• findAncestorWidgetOfExactType< T extends Widget >

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).

Acinaciform

Answer 2

The main difference for performances is not due to the fact that findAncestorWidgetOfExactType() searches for any Widget subclass, while dependOnInheritedWidgetOfExactType() searches only for InheritedWidget subclass.

dependOnInheritedWidgetOfExactType() is less expensive because every widget (more precisely, every Element) keeps a Map (in the field _inheritedWidgets) of all ancestor InheritedWidgets, indexed by their type. Then dependOnInheritedWidgetOfExactType() doesn't search in the widget's tree, but only in this map.

Useful articles:

"How does Flutter InheritedWidget work?"

"Widget - State - Context - InheritedWidget" (of Didier Boelens, an article's author cited also in flutter.dev)

Drabble

Thanks alot , that 'dependOn' part wasn't very clear to me, the medium article clarified everything Thanks again. So, the 'findAncestor' does linear searching for a widget type that matches the given type in the widgets tree that's why it is O(N) , and the 'dependOn' - directly - fetches the right widget from the map ( in each element ) with the given type as a 'key' that is why it is O(1). – Acinaciform