-1
$\begingroup$

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct.

I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$

(a)                             
   sum=0;
   for ( i =0; i<n ; i +=10)          
      sum++;


(b) 
    sum=0;
    for ( i =0; i<n*n;++ i )
        for ( j =n ; j >0;--j )
            ++sum;

(c)
    sum=0;
    for ( i =0 , j =n ; i<j ;++ i , j --)
        ++sum;

(d)
    int function (long n){
       int sum = 0 ;
       for (;n>0;n/=2){
        sum+=n%2;
       }
       return sum;
    }
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W.♦ Mar 2 '18 at 18:43
  • $\begingroup$ Cross-posted: stackoverflow.com/q/49063636/781723, cs.stackexchange.com/q/88825/755. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$ – D.W.♦ Mar 2 '18 at 18:46
1
$\begingroup$

As you said:

a)running n/10 times therefore O(n)

b)outer loop n^2 times inner loop n times hence O(n^3)

c)Runs n/2-1 times :hence O(n)

d)Runs n/(2^k)=1 where k is some integer(no of times loop runs) on solving we get k=O(logn) , in base 2.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I'm confused. You've marked your whole answer up as quotation but it doesn't seem to be one. $\endgroup$ – David Richerby Mar 2 '18 at 19:55
2
$\begingroup$

c) is incorrect.

It looks like you are saying it is $O(n^{\frac{1}{2}})$ or $O(\sqrt{n})$. That cannot be the case. You are adding one to $i$ and subtracting one from $j$ on each loop iteration. That means the counters should meet in the middle.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.