This question already has an answer here:

I have a graph which looks something like below Search

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; 
        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

        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


marked as duplicate by David Richerby, Evil, hengxin, Rick Decker, Juho May 5 '17 at 20:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Could you replace the (extremely verbose) code with pseudocode? $\endgroup$ – David Richerby Apr 27 '17 at 17:05
  • $\begingroup$ The worst-case time complexity is big theta of the depth of the DAG. $\endgroup$ – Yuval Filmus May 3 '17 at 6:46

This answer is under the assumption that findSubstring() is $O(1)$, which it realistically is not. Notice that at each iteration, when you make a step down to the next level in the graph, the problem size is being reduced by a factor of 2. That is, the amount of possible solutions is being reduced by a factor of 2. Specifically this is because the size of the strings duplicate at each layer down into the graph. So at any rate, if you have a string of length $n$, it will take $\log n$ steps to reach a solution using this algorithm. Furthermore, the string length must be a power of 2. This is a bit easier to visualize if you split your graph into its equivalent binary tree:

binary tree rep

This is a valid representation because each time you go left or right, you are cutting yourself off from impossible solutions, and that is exactly what happens in binary trees.

$\log n$ is just the time bound with respects to the length of the string however. You must also consider the height of the graph (number of nodes from start to some end node). If we have a full graph of this format (every layer is filled). If the graph is of height $h$, you could imagine this graph as the top left half of an $h \times h$ grid if you cut it in half along the diagonal. This means for a graph of height $h$, we have $h \cdot h / 2$ nodes in the graph.

So now we have two scenarios, (1) the upper bound of string length ends the algorithm or (2) the upper bounds of graph height ends the algorithm. Which gives a result:

$O(max(\log n, \sqrt{|V|})) = O(\log n + \sqrt{|V|})$ where $n$ is the length of the input string and $|V|$ is the number of nodes in the graph.

Another similar approach to this problem that you might be able to utilize:

If you know the length of the string (assuming it's given), you know the precise layer of the graph it will be in. If you can get to that layer in constant time (not sure if this will be possible with your setup), you might be able to use a different greedy approach to binary search for the solution inside that layer.

A string of length $n$ will be at level $\log n + 2$ in the graph. At level $l$ of the graph there will be $l$ nodes (possible solutions). So if the string is at level $\log n + 2$, there are $\log n + 2$ nodes at that level. If you can binary search somehow (an exercise for the reader) through that layer, you might be able to get a $\log \log n$ solution.

  • $\begingroup$ I have a slight confusion which is by how much does $n$(i.e. number of nodes) increase in the binary tree compared to the graph I have given at each level.What will be the aggregate.And is your $log n$ considering the number of nodes in the binary tree ? I want to find the complexity in the number of nodes in the given graph $\endgroup$ – Romantic Electron Apr 27 '17 at 18:47
  • $\begingroup$ At each level in the binary tree, clearly the amount of nodes will duplicate. At each level in your graph each level increases by 1. This is consistent between the two structures because the binary tree contains repeated nodes that would be considered the same node in the graph. If you have a graph of height $h$ (each level filled completely), you could imagine it like the top left diagonal of an $h \times h$ grid. Making left/right decisions to get to some node in the final row then takes $h$ time. $\endgroup$ – ryan Apr 27 '17 at 19:03
  • $\begingroup$ Ok I have got it , Even if the nodes get doubled up it will still remain $n$ because constants get ignored and the complexity will remain $\log n$ $\endgroup$ – Romantic Electron Apr 27 '17 at 19:04
  • $\begingroup$ To clarify, it's $\log n$ where $n$ is the length of the input string. To get this in terms of nodes in the graph, refer to my last comment about the height of the graph (# of nodes can be put in terms of height and height can be put in terms of length of the string). $\endgroup$ – ryan Apr 27 '17 at 19:06
  • 1
    $\begingroup$ I apologize, don't let that last comment confuse you. I believe this algorithm is easier to explain in terms of input string size, because is truly what will bound the running time. Although if you want to put it in terms of the number of nodes in the graph, it can at most traverse the height of the graph. If we have a graph of height $h$, there will be $h \cdot h / 2$ nodes in the graph. Set that equal to $|V|$ and you get that the height is $\sqrt{2 |V|}$. $\endgroup$ – ryan Apr 27 '17 at 19:21

No. The running time is not $O(\log n)$. The running time is at least $\Omega(n)$. In each iteration of the loop, you call findSubStringIndex() to check whether the string in a node is a substring of s (where $n$ is the length of the string s). That check can take $\Theta(n)$ time.

This appears to be an inefficient data structure, and it appears there are better choices -- e.g., a hashtable, a trie.

  • 1
    $\begingroup$ There was an assumption that findSubStringIndex() takes $O(1)$. Without that assumption then no it would not be $O(\log n)$, but with the assumption, I believe $\log n$ time complexity should still be possible. $\endgroup$ – ryan Apr 27 '17 at 17:44
  • 2
    $\begingroup$ @Ryan, but it doesn't take $O(1)$ time. That assumption is bogus. If you assume that $1+1=3$, you can infer that I am the pope. In other words, if you start from faulty assumptions, you can come to all sorts of mistaken conclusions. $\endgroup$ – D.W. Apr 27 '17 at 17:45
  • $\begingroup$ I see what you mean, that's a fair point and concern. I still think it's worth noting, in the context of a constant time decision maker (decision to go left or right) a $\log n$ time complexity is possible. Although in this context that would not be possible because findSubstring is not constant time. Thanks for pointing that out, I appreciate the remarks. $\endgroup$ – ryan Apr 27 '17 at 17:56
  • $\begingroup$ @D.W. Even if something is unrealistic you should stick to the question.If for a moment someone asks you to imagine something , it doesn't mean that you've to look if it's possible or not .Just imagine it's there.My real confusion is how to start considering algorithmic analysis for this search in terms of total nodes $\endgroup$ – Romantic Electron Apr 27 '17 at 18:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.