Time complexity of finding a triangle in undirected graph Recently I posted the following solution on Stack Overflow and comments made me to rethink about the time complexity of my solution which I am sure is \$O(V+E)\$. Please suggest reasons as to why I am wrong.

import java.util.*;
class Triangle
{
 static ArrayList&lt;LinkedList&lt;Integer&gt;&gt; g; 
 static int []visited;
 static int []level;
 static int []parent;
 static Queue&lt;Integer&gt; q=new LinkedList&lt;Integer&gt;();
 public static void create_graph()
 {
     int n,i,k,j;
     Scanner s=new Scanner(System.in);
     System.out.println("enter the value of number of vertices");
     n=s.nextInt();
     visited=new int[n];
     level=new int[n];
     parent=new int[n];
     for(i=0;i&lt;n;++i)
      {visited[i]=0;level[i]=-1;}
     g=new ArrayList&lt;LinkedList&lt;Integer&gt;&gt;();
     for(i=0;i&lt;n;++i)
     {
         g.add(new LinkedList&lt;Integer&gt;());
         System.out.println("enter the number of vertices adjacent to "+ (i)+" and what are they?" );         
         k=s.nextInt();
         for(j=1;j&lt;=k;++j)
           g.get(i).add(s.nextInt());
     }      
 } 
 public static boolean BFS(int so,int l)
 {  
        int i;   
        visited[so]=1;
        q.add(so);
        level[so]=l;
        while(q.size()!=0)
        {
            i=q.poll();            
            for(int e:g.get(i))
             {
                if(visited[e]==0)
                {visited[e]=1;
                 level[e]=level[i]+1;                 
                 q.add(e);
                 parent[e]=i;
                }
                else if(level[e]==level[i]&amp;&amp;parent[e]==parent[i])
                 return true;
             }
        }
        return false;          
 }
 public static void main(String []args)
 {
      int so,i;      
      Scanner s=new Scanner(System.in);
      create_graph();
      if(BFS(0,0))
       System.out.println("The graph contains a triangle");
      else  System.out.println("The graph does not contain a triangle");      
 }
}
Before I'll get to your timecomplexity let me tell you something:

Your code screams for a lint:


class Triangle
{
 static ArrayList&lt;LinkedList&lt;Integer&gt;&gt; g;



this part should become:

class Triangle {
    static ArrayList&lt;LinkedList&lt;Integer&gt;&gt; g;


no wait scratch that:


Whenever possible - specify visibility
Program against interfaces
Use speaking variables


Okay let's try again

public class Triangle {
    private static List&lt;List&lt;Integer&gt;&gt; graph;


same goes for your int[]s. On a very related note, you should encapsulate state into a class and not into the static context, where everything can modify it. Drop the static modifiers you use.

Use the final keyword to signal immutability. Use it wherever possible to reduce risk of misassigning variables.

The initialization blocks become:

private final List&lt;List&lt;Integer&gt;&gt; graph = new ArrayList&lt;List&lt;Integer&gt;&gt;();
private int[] visited;
private int[] level;
private int[] parent;
private final Queue&lt;Integer&gt; queue = new LinkedList&lt;Integer&gt;();




I usually prefer to add an empty line before a method head to help in recognizing it as new method. And also respect Java naming conventions for method names. This means: no snake_case and no SHOUTCASE. camelCase is the way to go:

public void createGraph() {


Also respect the braces placement of Java conventions. On a related note keep nice spacing around your operators. Cramping code together doesn't help readabiltiy and the times of scarce memory, where every unnecessary space was a wasted Byte are over:

Scanner s = new Scanner();


is preferrable over:


Scanner s=new Scanner();



same goes for all the operations you're doing...

While we're at Scanner. One of these Scanners is not used, neither is ever closed. Close your resources with try-with-resources, remove all of your unused variables and declare variables as close as possible to their usage.

This gets rid of:

int so, i;
Scanner s=new Scanner(System.in);
int n,i,k,j;


To make things clear, this is what your code looks like in my IDE right now:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

class Triangle {

    private final List&lt;List&lt;Integer&gt;&gt; graph = new ArrayList&lt;List&lt;Integer&gt;&gt;();
    private int[] visited;
    private int[] level;
    private int[] parent;
    private final Queue&lt;Integer&gt; queue = new LinkedList&lt;Integer&gt;();

    public void createGraph() {
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.println("enter the value of number of vertices");
            int vertexCount = scanner.nextInt();
            visited = new int[vertexCount];
            level = new int[vertexCount];
            parent = new int[vertexCount];
            for (int i = 0; i &lt; vertexCount; ++i) {
                visited[i] = 0;
                level[i] = -1;
            }
            for (int i = 0; i &lt; vertexCount; ++i) {
                graph.add(new LinkedList&lt;Integer&gt;());
                System.out.println("enter the number of vertices adjacent to " + (i) + " and what are they?");
                int k = scanner.nextInt();
                for (int j = 1; j &lt;= k; ++j) {
                    graph.get(i).add(scanner.nextInt());
                }
            }
        }
    }

    public boolean triangleCheck(int so, int l) {
        visited[so] = 1;
        queue.add(so);
        level[so] = l;
        while (queue.size() != 0) {
            int i = queue.poll();
            for (int e : graph.get(i)) {
                if (visited[e] == 0) {
                    visited[e] = 1;
                    level[e] = level[i] + 1;
                    queue.add(e);
                    parent[e] = i;
                }
                else if (level[e] == level[i] &amp;&amp; parent[e] == parent[i])
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Triangle tri = new Triangle();
        tri.createGraph();
        if (tri.triangleCheck(0, 0)) {
            System.out.println("The graph contains a triangle");
        }
        else {
            System.out.println("The graph does not contain a triangle");
        }
    }
}




By now you're probably asking yourself "Why did I even come here, I wanted to know about time-complexity"... The answer is. I couldn't even understand your code until just now. 

Honestly I still now have problems, bit I think you should get down to   \$O(V)\$, under the assumption that this code actually produces correct results..