CODEWITHSUNDEEP
algorithmtime-complexity
NTL
NTL

Reputation: 1007

Confusion with O(1)

I am a little bit confused about what exactly O(1) means in terms of algorithms. The algorithm has a constant time, but I am not exactly sure what exactly qualifies as a constant time. For example, I have two algorithms

public void addOne(String string) {
    LinkedList tempList = new LinkedList();
    tempList.add(string);
    mainList.add(tempList);
    size[0]++;
}

and 

public void addTwo(String string, String string2) {
    LinkedList tempList = new LinkedList();
    tempList.add(string);
    tempList.add(string2);
    mainList.add(tempList);
    size[1]++;
}

Would both of these algorithms be O(1)? I'm assuming if there was a numerical variable which would cause it to loop n amount of times, then it would be O(n)?

ie. (not necessarily a practical example, as in it'd add the same string value, but should give an idea)

public void add(String string, int n){
    LinkedList tempList = new LinkedList();
    for (int i=0; i<n; i++){
         tempList.add(string);
    }
    mainList.add(tempList);
}

Upvotes: 1

Views: 111

Answers (3)

Tejash Desai
Tejash Desai

Reputation: 466

Note that Big O doesn't define the time that your program takes, it only defines the growth rate of your program i.e how will the computation time increase with the increase in the number of inputs.

In the first 2 examples, the number of statements executed remains the same even if you increase the number of inputs. In other words, even if you add, say string3 in example 2, number of executable statements still remains 5, making its computation a constant. i.e. its computation time will not increase with the increase in the number of inputs (independent of inputs). Thus, it is O(1).

However, in the third example, you are using a loop which runs n times, n is passed as an input. Therefore, number of executable statements increases with n linearly. So if you pass n as 155, execution becomes approx 155 times as much as it would be if n was 1. Thus, it is O(n).

Upvotes: 0

pjs
pjs

Reputation: 19855

"...what exactly qualifies as a constant time."

If you have a function, or a block of code, where the amount of time required to complete its task never exceeds some constant no matter what arguments you pass to the function, or how the amount of data in the container(s) being manipulated varies, then that task qualifies as constant time.

Upvotes: 1

amit
amit

Reputation: 178491

Your observations are correct1.

Both of the first two methods are O(1), since you can find a hard constant for the number of operations it has to do (This constant might vary between different machines, but it will still be constant), and thus it is O(1).

The last method is indeed O(n), as you have n insertions, each taking constant time, but together they take time which is linear in n.

(1) Assuming here mainList implements add() in O(1) as well, otherwise - it will be the bottleneck.

Upvotes: 2

Related Questions