Big-O Analysis - While Loops

Question

I was given a programming problem that given an array, determine if it is a post order traversal of a binary tree. My solution is as follows:

public static boolean isPostOrder(int[] array) {

    int root = array[array.length - 1];

    int i = 0;

    while(array[i] < root) {
        i++;
    }

    while(array[i] > root) {
        i++;
    }

    return i == array.length - 1;

}

I am trying to understand Big O. I have read this tutorial:

What is a plain English explanation of "Big O" notation?

However, I am still confused about addition and the while loops. I'm assuming in this case my while loops are O(1) since we are just comparing a value in an array to an integer, or am I wrong about this?

Now the addition is also O(1) because we are just adding 1 to some integer 1, right?

Therefore, is this an O(1) solution or am I missing something?

The standard while loop you have presented is considered O(n). The addition is O(1). If you do something once over, it's O(1). If you do something `n` times, it's O(n). — Compass, Oct 31 '14 at 18:07
Ah okay. I also realized that my solution to the problem isn't correct too. Thanks! — Sameer, Oct 31 '14 at 18:11

score 0 · Answer 1 · answered Oct 31 '14 at 18:11

0

You algorithm runtime has a lineair connection to the input size because you loop through the elements of the input array. This makes it that your algorithm is O(n). If you wouldn't have had any loops, it would have been O(1) = constant access time.

answered Oct 31 '14 at 18:11

Joren

3,068
25
44

score 0 · Answer 2 · answered Oct 31 '14 at 18:13

The basic idea behind Big-O notation is to estimate the number of basic operations you algorithm performs, and how the size of the input affects it.

Here, your basic operation is to increment i (++i). You're iterating over an array of size N, and in the worst case, you go over all of it. So, this algorithm has a O(N) complexity.

Big-O Analysis - While Loops

2 Answers2