Algorithm complexity without loops?

Question

I am sorry for asking such a Dummy question but I can't seem to find the answer. I know how to calculate the complexity of an algorithm ( O() ) when there are loops'n stuff, but in this case I have difficulty wrapping my head around it. The language is C++.

Here's the code :

int calculate(int k, int n){ // Code C++
    int firstSequenceEnd = k-1;
    int sumAk = ((1 + (firstSequenceEnd))*(firstSequenceEnd) ) >> 1;
    return (1 << n-k)*sumAk;
}

Thank you in advance !

Following @OliCharlesworth's question: in this code the number steps does not depend on the input. It does not loop, does not recurse, just a static calculation. — fejese
– fejese, Commented Jun 29, 2014 at 16:50
That is kinda my question, does 1 << n-k counts as one or n-k ? — Peter Marinov
– Peter Marinov, Commented Jun 29, 2014 at 16:50

David G · Accepted Answer · 2014-06-29 17:14:56Z

4

When there are no loops then we are talking about O(1).

edited Jun 29, 2014 at 17:14

David G

97.6k41 gold badges173 silver badges258 bronze badges

answered Jun 29, 2014 at 16:50

yossico

3,5315 gold badges45 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Oliver Charlesworth Over a year ago

This is overly-simplistic; recursive code will generally be greater than O(1) for example, even without loops.

yossico Over a year ago

@OliCharlesworth I agree with your comment, But there is no recursion on his example. And a recursion will be transferred (on machine code ) to loop (based on the stack but still - a loop)

Collectives™ on Stack Overflow

Algorithm complexity without loops?

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related