I have a graph which looks something like below
I am searching for a given string s
going down such that at every node it makes a decision (either to visit the left node or right). The code goes something like this.
String s=input;
Node CurrentNode=start;
int rightSubstringIndex=-1;
int leftSubstringIndex=-1;
while(true){
if(CurrentNode.getValue()==s){
return 1;//indicating that the string was found in the graph
}
if(CurrentNode.right==null){//there won't be a node with only one child so either both child nodes are there or there is no child
return 0;//indicating that the string was not found in the graph
}
rightSubstringIndex=findSubStringIndex(CurrentNode.right.getValue(),s);
leftSubstringIndex=findSubStringIndex(CurrentNode.left.getValue(),s);
if(rightSubstringIndex<leftSubstringIndex){
CurrentNode=CurrentNode.right;//go towards the right node
}
else if(leftSubstringIndex<rightSubstringIndex){
CurrentNode=CurrentNode.left;//go towards the left node
}
else{//i.e when rightSubstringIndex==1000 && leftSubstringIndex==1000
return 0://indicating that the string was not found in the graph
}
}
findSubstringIndex(a,b)
returns the index in the string array b
where the substring a
starts . Returns 1000 if the the substring a
doesn't occur in b
(assuming that there will not be a string having length greater than 1000 characters).The time complexity of function findSubstring(a,b)
is assumed to be $O(1)$.
I am interested in finding out the time complexity of the above described algorithm.I know that if it was a binary tree and I had to look up for the string using a similar strategy the complexity will be $O(logN)$. I don't know how to think of complexity in terms of number of nodes in this scenario.
I am not very good at theory so kindly don't go hard on me