CODEWITHSUNDEEP
javaalgorithmbig-ocomputer-science
BlueLink77
BlueLink77

Reputation: 29

Confused on Big-O Notation

Alright I have a quick question for all of the programmers that are preusing for an easy question.

For my Computer Science II class we are going over Big-Oh notation and I've got most of it down, but I am still confused on some of the semantics of the examples.

Everything here is written in Java.

My professor gave us these examples in class, but my luck, I didn't write down the answers.

a)

int count = 0; 
    for (int i = 1; i <= n; i++) 
        for (int j = n; j > 1; j-­--­-) 
            for (int k = 1; k < n; k = k + 2) 
                count++;

b)

int count = 0; 
for (int i = 1; i <= n; i++) 
    for (int j = n; j > 1; j-­--­-) 
        for (int k = 1; k < 1000; k = k + 2) 
            count++;

c)

int count = 0; 
    for (int i = 1; i <= 1000000; i++) 
        for (int j = i; j > 500; j-­--­-) 
            for (int k = 1; k < 10500; k = k + 2) 
                count++;

d)

int count = 0; 
int j = 1; 
for (int i = 1; i < n; i++) { 
        while (j < n) { 
            j++;
            count++; 
        } 
        j = 1; 
    }

e)

int count = 0; 
int i = n; 
while (i > 1) 
{ 
    count++; i = i / 2; 
}

Alright so here are my answers/thought processes:

a) N * N * (N / 2) = N^3/2, All simplifies to a O(N^3) notation

b) N * N * 500, All simplifies to O(N^2)

c) This is the one that I am majorly confused on you have three for loops, but all iterate the exact number of times. My guess here is O(1), but I have no idea...

d) N * N = N^2, So O(N^2)

e) Divides by half each time, so log(n) = O(log(n)) [both base 2]

So can anyone check through my thought process and see if I am missing anything? Thank you so much in advance!

Upvotes: 2

Views: 723

Answers (2)

Mike Samuel
Mike Samuel

Reputation: 120586

In all these examples, count is incremented once for each work unit. If you can figure out the relationship between count and n, then you know the asymptotic order of the program.

It's good you worked things out. The next step is to check your calculations against reality. Run the code for different values of n, print out count, and check your work against real data.

Upvotes: 0

Dan
Dan

Reputation: 724

Yeah (C) is O(1) because it's all constants.

Upvotes: 1

Related Questions