CODEWITHSUNDEEP
javaperformancebig-o
Jazib Khan
Jazib Khan

Reputation: 21

Calculate the running time in Big-O notation

1 int sum=0;
2 long start = System.currentTimeMillis();
3 for (int i = 1; i <= N; i++) {
4 for (int j = 1; j <= N; j++) {
5 sum=sum+1;}}
6 long stop = System.currentTimeMillis();
7 long elapsed = (long)(stop - start);

I am stuck on this question I know lines 1,2,5,6 and 7 are primitive operations they run at O(1) constant time. I am having doubt about the loops I think it is O(n^2) can anyone elaborate on this thanks.

Upvotes: 1

Views: 327

Answers (2)

akmin04
akmin04

Reputation: 697

Here's a comment from Reddit that gave good examples of some different O runtimes.

link

In the scenario, a teacher has lost his/her pen and is trying to find out which student took it.

O(n2): I question a student and ask them, "Does Jeff have the pen? No? Does Bob have the pen?" And so on, naming each student. If I don't get the answer from the first student, I move on to the next one. In the worst case I need to ask n2 questions - questioning each student about each other student.

O(n): I ask each student if they have the pen. If not, I move on to the next one. In the worst case I need to ask n questions.

O(log n): I divide the class in two, then ask: "Is it on the left side, or the right side of the classroom?" Then I take that group and divide it into two and ask again, and so on. In the worst case I need to ask log n questions.

I should also add on that O(1) is basically asking the whole class "Who has my pen?" No matter how many people are in the class, asking who has the pen will take the same amount of time, making it constant.

Upvotes: 0

potato
potato

Reputation: 1123

You are right, one for loop alone is O(n) because it's running time is linearly proportional to the size of the input, and together with the second loop it is O(n^2) because you repeat an O(n) function n times.

Upvotes: 4

Related Questions