Member Avatar for Akira01

Hello all! First time poster here and I'm looking for a little help figuring out the time complexity of this program.

int y;

void p(int x)
{
    x = y - 1;
    y += x;
    cout << x << " " << y << endl;
    if (x<3) p(x);
    cout << x << " " << y << endl;
}

void main(void)
{
    int x;
    x = 0; y = 2; p(x); cout << x << " " << y << endl;
}

Thanks for any help you can give me!

  • 3 Contributors
  • 2 Replies
  • 349 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by Taywin
Member Avatar for geojia

O(1)

Member Avatar for Taywin

If the question asks for the whole program, then yes (O(3) == O(1)). Though, it is trivia if that is the question. If the problem is asking for the time complexity of the function, that will be a huge difference. The reason is that the function can go into an infinite loop if y is initialised to zero or a negative number.

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.