I'm studying for an exam and need to see if my answers for the following question is correct.
Give the bigO estimate for each code fragment in terms on n. method L has method signature void L(int n) & has execution time complexity of O(n). method C has method signature void C(int n) & has execution time complexity of O(1).

1.

while (n>0){
L(n);
n=n/2;
}

2.

if(a<b){
System.out.println(C(n) + L(n));
else { Sytem.out.println(C(n) - L(n)) }

3.

while(n>0){
C(n);
n = n/2;
}

I'm thinking for 1) O(nlogn), 2) O(n) and 3) O(logn). Not sure if i'm 100% correct though. Any help?

Recommended Answers

All 2 Replies

I have never been a fan of Big Oh estimation and I am pretty poor with it. Correct me if I am wrong.

1)
The execution time for the first exercise would be:
L(n) + L(n/2) + L(n/4) + L(n/8) + .... + L(n/n) approximately equal to 2n

^ Right you are, invisal. The big-Oh time complexity of (1) is in fact O(n). It would be O(nlogn) if it were the following:

m := n
while n > 0 do
   L(m);
   n := n / 2

And the answers for (2) and (3) are right on the money. Good job!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.