Complexity of my Algorithm

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, May 31 '17 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, May 31 '17 at 15:00
@JörgWMittag See also [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) and [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation) — Bernhard Barker, May 31 '17 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, May 31 '17 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, May 31 '17 at 16:20
If you look at the C++ specification, you can see how complexities are specified there, e.g. "O(N logN) comparisons, where N = last - first." Note how it specifically names *what* it is counting ("comparisons") and it also specifically says what "N" is. "At most N log2(N) comparisons, where N = last - first, but only N log N comparisons if there is enough extra memory." Here you can see that the bound is specified *precisely*, without the use of approximations such as Bachmann-Landau-Notation. "Approximately (last - first) * log(min(last - first, result_last - result_first)) comparisons". — Jörg W Mittag, May 31 '17 at 16:26

score 5 · Accepted Answer · answered May 31 '17 at 13:48

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 '17 at 13:48

Kaidul

15,409
15
81
150

Complexity of my Algorithm

1 Answers1