How to calculate the time complexity of a Java program?

Question

How can I calculate the time complexity of this program? Is there a more efficient solution?

public class MinJumpstoEnd {
    public static void main(String[] args) {
        
        int[] a = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
        //i is used for array elements & c to count jumps

        int i =0,c =0;
        int j = a[0];
        
        while(a.length-i > j) {
            if(a[i]==0) {
                System.out.println("Cant Reach");
            }

            i += j;
            c+=1;

            j = a[i]-1;
            System.out.println("j:"+j);
        }
        System.out.println("Jumps : "+c);
    }
}

Worst case is that it'll step on every element in the array, so _O(n)_. — Andreas, Jun 28 '21 at 08:16
Are negative inputs allowed? Are there any other requirements to the input? When O is hard to determin otherwise O(n). — Marlon, Jun 28 '21 at 08:16
What happens for the input `1, 1, 1, 1, 1, 1`? `j` will become `0` and `i` will remain at `1`. And the loop will never stop!? — luk2302, Jun 28 '21 at 08:20
Does this answer your question? [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) — Welbog, Jun 28 '21 at 22:49

Manan Modi · Answer 1 · 2021-08-11T07:18:49.950

0

In the worst case your i has to traverse the whole array, and hence it would be O(n). It might happen that it might skip few elements in between while traversing but still it would be a linear function.

edited Aug 11 '21 at 07:18

answered Aug 08 '21 at 07:23

Manan Modi

1
1

I don't think this answers OP's question (at least not in detail). They are asking how to calculate it, and not which complexity measurements apply to which types of algorithms. Though that helps, it may not be obvious to them how to connect the dots. – ryanwebjackson Aug 08 '21 at 20:44

How to calculate the time complexity of a Java program?

1 Answers1