Click here to Skip to main content
15,887,444 members
Home / Discussions / Algorithms
   

Algorithms

 
GeneralRe: Wildcard Matching Routine Pin
Richard Andrew x6426-Dec-21 1:32
professionalRichard Andrew x6426-Dec-21 1:32 
AnswerRe: Wildcard Matching Routine Pin
englebart8-Feb-22 16:36
professionalenglebart8-Feb-22 16:36 
GeneralRe: Wildcard Matching Routine Pin
trønderen9-Feb-22 6:35
trønderen9-Feb-22 6:35 
GeneralRe: Wildcard Matching Routine Pin
englebart9-Feb-22 15:37
professionalenglebart9-Feb-22 15:37 
GeneralRe: Wildcard Matching Routine Pin
Eddy Vluggen9-Feb-22 16:10
professionalEddy Vluggen9-Feb-22 16:10 
GeneralRe: Wildcard Matching Routine Pin
trønderen10-Feb-22 6:03
trønderen10-Feb-22 6:03 
GeneralRe: Wildcard Matching Routine Pin
englebart10-Feb-22 9:14
professionalenglebart10-Feb-22 9:14 
QuestionTime Complexity of following method? Pin
Member 1269110623-Nov-21 4:09
Member 1269110623-Nov-21 4:09 
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<Set<Integer>> edgeSetList = "converted first edges element to set of Integer"

        // iterate rest of edges elements -A
        for(int i=1;i<edges.length;i++){

            Set<Integer> 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<Integer> 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<Integer> 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.length) = O( n! / 2! * (n-2)! ) = O( ( n * (n-1)) / 2 ) = O( n^2 - n / 2) ==> O(n^2)

Please feel free to share also consider me a complete noob for Algorithm. Just started learning formally.

modified 24-Nov-21 1:01am.

AnswerRe: Time Complexity of following method? Pin
Greg Utas23-Nov-21 5:17
professionalGreg Utas23-Nov-21 5:17 
GeneralRe: Time Complexity of following method? Pin
Member 1269110623-Nov-21 18:22
Member 1269110623-Nov-21 18:22 
AnswerRe: Time Complexity of following method? Pin
Member 1269110623-Nov-21 19:05
Member 1269110623-Nov-21 19:05 
AnswerRe: Time Complexity of following method? Pin
Member 1546299610-Dec-21 5:08
Member 1546299610-Dec-21 5:08 
QuestionNUMBER OF COMBINATIONS OF THE ARRANGEMENT OF CAPS Pin
Member 1543482417-Nov-21 13:48
Member 1543482417-Nov-21 13:48 
AnswerRe: NUMBER OF COMBINATIONS OF THE ARRANGEMENT OF CAPS Pin
Greg Utas23-Nov-21 5:14
professionalGreg Utas23-Nov-21 5:14 
QuestionC# Pin
Member 153810723-Oct-21 21:36
Member 153810723-Oct-21 21:36 
AnswerRe: C# Pin
Richard MacCutchan3-Oct-21 21:49
mveRichard MacCutchan3-Oct-21 21:49 
QuestionFunction of algorithm Pin
danindya1-Sep-21 15:52
professionaldanindya1-Sep-21 15:52 
AnswerRe: Function of algorithm - Spammer Pin
Dave Kreskowiak1-Sep-21 16:23
mveDave Kreskowiak1-Sep-21 16:23 
QuestionHelp with allocation algorithm Pin
Cynthia Moore24-Aug-21 19:43
Cynthia Moore24-Aug-21 19:43 
AnswerRe: Help with allocation algorithm Pin
Gerry Schmitz25-Aug-21 18:49
mveGerry Schmitz25-Aug-21 18:49 
GeneralRe: Help with allocation algorithm Pin
Cynthia Moore25-Aug-21 19:42
Cynthia Moore25-Aug-21 19:42 
GeneralRe: Help with allocation algorithm Pin
Gerry Schmitz26-Aug-21 4:37
mveGerry Schmitz26-Aug-21 4:37 
GeneralRe: Help with allocation algorithm Pin
Cynthia Moore26-Aug-21 7:16
Cynthia Moore26-Aug-21 7:16 
AnswerRe: Help with allocation algorithm Pin
BillWoodruff28-Aug-21 16:09
professionalBillWoodruff28-Aug-21 16:09 
QuestionWhich is the more preferred approach for novice coders, depth first search, or, breadth first search? Pin
the prestige city23-Jul-21 1:23
professionalthe prestige city23-Jul-21 1:23 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.