Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • World
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor

  • Default (No Skin)
  • No Skin
Collapse
Code Project
CODE PROJECT For Those Who Code
  • Home
  • Articles
  • FAQ
Community
  1. Home
  2. General Programming
  3. Algorithms
  4. Time Complexity of following method?

Time Complexity of following method?

Scheduled Pinned Locked Moved Algorithms
algorithmsdata-structuresjsonquestion
5 Posts 3 Posters 48 Views 1 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • U Offline
    U Offline
    User 12657536
    wrote on last edited by
    #1

    Here edges is a String array representing a set of space separated integer pair elements e.g. "e1 e2" where 0 < e1!=e2 <= n n is an integer, let's say ranging 0 < n <= 100000

    public int sumSqrtCeil(int n, String[] edges){
    ...

        List\> edgeSetList = "converted first edges element to set of Integer"
    
        // iterate rest of edges elements -A
        for(int i=1;i nodeDuo = "converted this edges element to set of Integer"
    
            boolean found = false;
            //search for nodeDuo in set elements of edgeSetList
    
            //iterate the nodeDuo 2 element set -B
            for(Integer e : nodeDuo){
                //iterate the edgeSetList containing a linked set collection -C
                for (Set edgeSet : edgeSetList) {
                    found = edgeSet.contains(e);
                    if (found) {
                        break;
                    }
                }
                if(found) break;
            }
    
            if(!found){
    
                //if nodeDuo has no element common to any element of edgeSetList then add a new set
    
                indexOfEdgeSetList++;
                edgeSetList.add(nodeDuo);
            }
            else{
                //else add nodeDuo to the existing set element of edgeSetList in which any of nodeDuo elements were found.
                edgeSetList.get(indexOfEdgeSetList).addAll(nodeDuo);
            }
        }
    
    
        Set linkedNodes =         //identify a set of all nodes which are linked to a different node(s)
    
        //Add 1 for each unit nodes (the nodes which are no linked to any other nodes) -D
        for(int i=1;i<=n;i++){
            if(!linkedNodes.contains(i)) output+=1;
        }
    
        // Add ceil of square root of 'node count' of each linked set in linked nodes set collection -E
        output += edgeSetList.stream().mapToInt(integers -> (int) Math.ceil(Math.sqrt(integers.size()))).sum();
        return output;
    }
    

    As per my understanding (updated) complexity should be- O( O(A) * O(B) * O(C) + O(D) + O(E) ) O( O(edges.length) * O(2) * O(n/2) + O(n) + O(edges.length) ) O( O(edges.length) * O(n) + O(n) + O(edges.length) ) //constant removed O( O(n*edges.length) + O(n) + O(edges.length) ) //evaluate O( O(n^3) + O(n) + O(n^2) ) //evaluate O( O(n^3) ) //taking biggest factor O(n^3) - Final Time Complexity. where, O(edges.len

    Greg UtasG U M 3 Replies Last reply
    0
    • U User 12657536

      Here edges is a String array representing a set of space separated integer pair elements e.g. "e1 e2" where 0 < e1!=e2 <= n n is an integer, let's say ranging 0 < n <= 100000

      public int sumSqrtCeil(int n, String[] edges){
      ...

          List\> edgeSetList = "converted first edges element to set of Integer"
      
          // iterate rest of edges elements -A
          for(int i=1;i nodeDuo = "converted this edges element to set of Integer"
      
              boolean found = false;
              //search for nodeDuo in set elements of edgeSetList
      
              //iterate the nodeDuo 2 element set -B
              for(Integer e : nodeDuo){
                  //iterate the edgeSetList containing a linked set collection -C
                  for (Set edgeSet : edgeSetList) {
                      found = edgeSet.contains(e);
                      if (found) {
                          break;
                      }
                  }
                  if(found) break;
              }
      
              if(!found){
      
                  //if nodeDuo has no element common to any element of edgeSetList then add a new set
      
                  indexOfEdgeSetList++;
                  edgeSetList.add(nodeDuo);
              }
              else{
                  //else add nodeDuo to the existing set element of edgeSetList in which any of nodeDuo elements were found.
                  edgeSetList.get(indexOfEdgeSetList).addAll(nodeDuo);
              }
          }
      
      
          Set linkedNodes =         //identify a set of all nodes which are linked to a different node(s)
      
          //Add 1 for each unit nodes (the nodes which are no linked to any other nodes) -D
          for(int i=1;i<=n;i++){
              if(!linkedNodes.contains(i)) output+=1;
          }
      
          // Add ceil of square root of 'node count' of each linked set in linked nodes set collection -E
          output += edgeSetList.stream().mapToInt(integers -> (int) Math.ceil(Math.sqrt(integers.size()))).sum();
          return output;
      }
      

      As per my understanding (updated) complexity should be- O( O(A) * O(B) * O(C) + O(D) + O(E) ) O( O(edges.length) * O(2) * O(n/2) + O(n) + O(edges.length) ) O( O(edges.length) * O(n) + O(n) + O(edges.length) ) //constant removed O( O(n*edges.length) + O(n) + O(edges.length) ) //evaluate O( O(n^3) + O(n) + O(n^2) ) //evaluate O( O(n^3) ) //taking biggest factor O(n^3) - Final Time Complexity. where, O(edges.len

      Greg UtasG Offline
      Greg UtasG Offline
      Greg Utas
      wrote on last edited by
      #2

      You might have a better chance of getting a response if you stated the algorithm in the more general style of most textbooks rather than in C#, which not all readers understand.

      Robust Services Core | Software Techniques for Lemmings | Articles
      The fox knows many things, but the hedgehog knows one big thing.

      <p><a href="https://github.com/GregUtas/robust-services-core/blob/master/README.md">Robust Services Core</a>
      <em>The fox knows many things, but the hedgehog knows one big thing.</em></p>

      U 1 Reply Last reply
      0
      • Greg UtasG Greg Utas

        You might have a better chance of getting a response if you stated the algorithm in the more general style of most textbooks rather than in C#, which not all readers understand.

        Robust Services Core | Software Techniques for Lemmings | Articles
        The fox knows many things, but the hedgehog knows one big thing.

        U Offline
        U Offline
        User 12657536
        wrote on last edited by
        #3

        Thanks for advise. I am not a computer science grad, Let me have a look at an Algo book to study to update my question. Perhaps I may not need this forum to answer this question in the process.

        1 Reply Last reply
        0
        • U User 12657536

          Here edges is a String array representing a set of space separated integer pair elements e.g. "e1 e2" where 0 < e1!=e2 <= n n is an integer, let's say ranging 0 < n <= 100000

          public int sumSqrtCeil(int n, String[] edges){
          ...

              List\> edgeSetList = "converted first edges element to set of Integer"
          
              // iterate rest of edges elements -A
              for(int i=1;i nodeDuo = "converted this edges element to set of Integer"
          
                  boolean found = false;
                  //search for nodeDuo in set elements of edgeSetList
          
                  //iterate the nodeDuo 2 element set -B
                  for(Integer e : nodeDuo){
                      //iterate the edgeSetList containing a linked set collection -C
                      for (Set edgeSet : edgeSetList) {
                          found = edgeSet.contains(e);
                          if (found) {
                              break;
                          }
                      }
                      if(found) break;
                  }
          
                  if(!found){
          
                      //if nodeDuo has no element common to any element of edgeSetList then add a new set
          
                      indexOfEdgeSetList++;
                      edgeSetList.add(nodeDuo);
                  }
                  else{
                      //else add nodeDuo to the existing set element of edgeSetList in which any of nodeDuo elements were found.
                      edgeSetList.get(indexOfEdgeSetList).addAll(nodeDuo);
                  }
              }
          
          
              Set linkedNodes =         //identify a set of all nodes which are linked to a different node(s)
          
              //Add 1 for each unit nodes (the nodes which are no linked to any other nodes) -D
              for(int i=1;i<=n;i++){
                  if(!linkedNodes.contains(i)) output+=1;
              }
          
              // Add ceil of square root of 'node count' of each linked set in linked nodes set collection -E
              output += edgeSetList.stream().mapToInt(integers -> (int) Math.ceil(Math.sqrt(integers.size()))).sum();
              return output;
          }
          

          As per my understanding (updated) complexity should be- O( O(A) * O(B) * O(C) + O(D) + O(E) ) O( O(edges.length) * O(2) * O(n/2) + O(n) + O(edges.length) ) O( O(edges.length) * O(n) + O(n) + O(edges.length) ) //constant removed O( O(n*edges.length) + O(n) + O(edges.length) ) //evaluate O( O(n^3) + O(n) + O(n^2) ) //evaluate O( O(n^3) ) //taking biggest factor O(n^3) - Final Time Complexity. where, O(edges.len

          U Offline
          U Offline
          User 12657536
          wrote on last edited by
          #4

          Tried to update and make simpler to understand

          1 Reply Last reply
          0
          • U User 12657536

            Here edges is a String array representing a set of space separated integer pair elements e.g. "e1 e2" where 0 < e1!=e2 <= n n is an integer, let's say ranging 0 < n <= 100000

            public int sumSqrtCeil(int n, String[] edges){
            ...

                List\> edgeSetList = "converted first edges element to set of Integer"
            
                // iterate rest of edges elements -A
                for(int i=1;i nodeDuo = "converted this edges element to set of Integer"
            
                    boolean found = false;
                    //search for nodeDuo in set elements of edgeSetList
            
                    //iterate the nodeDuo 2 element set -B
                    for(Integer e : nodeDuo){
                        //iterate the edgeSetList containing a linked set collection -C
                        for (Set edgeSet : edgeSetList) {
                            found = edgeSet.contains(e);
                            if (found) {
                                break;
                            }
                        }
                        if(found) break;
                    }
            
                    if(!found){
            
                        //if nodeDuo has no element common to any element of edgeSetList then add a new set
            
                        indexOfEdgeSetList++;
                        edgeSetList.add(nodeDuo);
                    }
                    else{
                        //else add nodeDuo to the existing set element of edgeSetList in which any of nodeDuo elements were found.
                        edgeSetList.get(indexOfEdgeSetList).addAll(nodeDuo);
                    }
                }
            
            
                Set linkedNodes =         //identify a set of all nodes which are linked to a different node(s)
            
                //Add 1 for each unit nodes (the nodes which are no linked to any other nodes) -D
                for(int i=1;i<=n;i++){
                    if(!linkedNodes.contains(i)) output+=1;
                }
            
                // Add ceil of square root of 'node count' of each linked set in linked nodes set collection -E
                output += edgeSetList.stream().mapToInt(integers -> (int) Math.ceil(Math.sqrt(integers.size()))).sum();
                return output;
            }
            

            As per my understanding (updated) complexity should be- O( O(A) * O(B) * O(C) + O(D) + O(E) ) O( O(edges.length) * O(2) * O(n/2) + O(n) + O(edges.length) ) O( O(edges.length) * O(n) + O(n) + O(edges.length) ) //constant removed O( O(n*edges.length) + O(n) + O(edges.length) ) //evaluate O( O(n^3) + O(n) + O(n^2) ) //evaluate O( O(n^3) ) //taking biggest factor O(n^3) - Final Time Complexity. where, O(edges.len

            M Offline
            M Offline
            Member_15462996
            wrote on last edited by
            #5

            Micronaut here (Microverse Student) To get the complexity of this algorithm is actually quite simple, just check if there is an existing nested for loops and if those for loops actually depend on the input. For example: for(... input.length) { for(...input2.length) { } } this code's complexity will be the length of input1 * length of input2. and if they are the same, it will be the length^2. which is what we note by n².

            1 Reply Last reply
            0
            Reply
            • Reply as topic
            Log in to reply
            • Oldest to Newest
            • Newest to Oldest
            • Most Votes


            • Login

            • Don't have an account? Register

            • Login or register to search.
            • First post
              Last post
            0
            • Categories
            • Recent
            • Tags
            • Popular
            • World
            • Users
            • Groups