Complexity of my Algorithm [duplicate]

Question

The Question: Which Complexity has my function? and How to find time complexity of my algorithm?

The function checks if a given int array is sorted.

my Code:

public static boolean isSorted(double d[]){
boolean sortedAscending = true;
boolean sortedDescending = true;

boolean bool = false;
for (int i = 0; i < d.length-1; i++) {
    if(d[i] > d[i+1] && sortedAscending){
        sortedAscending = false;
        if(bool){
            break;
        }
        bool = true;
    }
    else if(d[i] < d[i+1]&& sortedDescending){
        sortedDescending = false;
        if(bool){
            break;
        }
        bool = true;
    }
}
return sortedAscending || sortedDescending;
}

It doesn't make sense to talk about "time complexity" without a machine model, a cost model, and a precise definition of what exactly it is that you are counting and what exactly you consider to be the "input size". So, what is your machine model? Is it a Turing Machine? Lambda Calculus? A RAM? What are you counting? Assignments? Equality tests? Lambda-Reductions? What is your cost model? Is < constant? Is it linear in the number of digits? — Jörg W Mittag
– Jörg W Mittag, Commented May 31, 2017 at 13:55
@JörgWMittag Time complexity is a fairly universally applicable concept that only tells you how things scale, thus is doesn't care about cost models, what you're measuring tends to be everything, input size can be defined in whichever way makes the most sense for the problem at hand (d.length in this case) and the machine model seems somewhat irrelevant if you assume everything executes sequentially (unless specified otherwise). "The time complexity of algorithm X is O(Y)" is something I've seen countless times from countless sources without any of the details you mentioned. — Bernhard Barker
– Bernhard Barker, Commented May 31, 2017 at 15:00
@JörgWMittag See also How to find time complexity of an algorithm and What is a plain English explanation of “Big O” notation? — Bernhard Barker
– Bernhard Barker, Commented May 31, 2017 at 15:02
@Dukeling: copying a list on a RAM is O(n), on a Turing Machine, it is O(n²). The lower bound for the worst-case time complexity of a comparison-based sort on a RAM is O(n log n) comparisons and swaps, but on a different machine model (e.g. where memory is linear, not random access), it is O(n²). So, yes, the machine model does matter. What also matters and is completely missing from the question is whether we are talking about worst-case, best-case, average-case, or amortized worst-case. Also, is the OP looking for the exact complexity function or is an approximation good enough? If yes, … — Jörg W Mittag
– Jörg W Mittag, Commented May 31, 2017 at 16:19
… how good should the approximation be? Is Bachmann-Landau-Notation good enough or should it be more precise? — Jörg W Mittag
– Jörg W Mittag, Commented May 31, 2017 at 16:20

Kaidul · Accepted Answer · 2017-05-31 13:48:47Z

5

This is just a one loop program with constant time execution in each iteration. Time complexity is linear - O(n) where n is the array length.

answered May 31, 2017 at 13:48

Kaidul

16k17 gold badges84 silver badges158 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Complexity of my Algorithm [duplicate]

1 Answer 1

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Linked

Related