2
$\begingroup$

After completing the time analysis for an algorithm I have been working on, I need some help to write its time complexity properly, let me describe how it works...

The algorithm has two inputs $x$ and $y$.

When $x < 15$, steps to solve are $2^y$, so I know this is $O(2^y)$.

However when $ x >= 15$, the steps to solve begin ramping down (from the $2^y$) at a rate of $-1\%$ as $x$ increases, up to $x < 50$ (don't know how to express this part)

And then, when $x>=50$ it flats out, and keep the same cost, that is $O(2^y*35\%)$, and doesn't matter what is the value of $x$ (as long as it is greater than $50$)

How to write a time complexity that has 3 delimited phases depending on the inputs?

$\endgroup$
4
$\begingroup$

You're interested in asymptotic behavior as $x$ increases without bound.

$O(.35 \times 2^y)$ is still $O(2^y)$.

$\endgroup$
2
$\begingroup$

When $x<15$, steps to solve are $2^y$, so I know this is $O(2^y)$.

It's also O(1).

Go back to the definition of $O$: small $x$ don't matter. In your case, pick $x_0 \geq 50$ and ignore the other cases.

That said, your question reads as if you looked at plots, not done a proper analysis. Be aware that plots (or other means of looking at finite samples) never prove any asymptotic property. You may want to peruse our reference questions.

$\endgroup$
  • $\begingroup$ described behavior is consistent with the algorithm implementation, there is an exact point that a optimization engages (depends on $x$), as $x$ grows, the optimization reduce the steps required by the algorithm, however, there is a balance point where the optimization reaches a maximum, and from there the step count stay flat for any $y$. (Not using plotting / guessing). I simplified the info to raise the questions, might be possible I simplified too much. $\endgroup$ – Jesus Salas Oct 9 '17 at 17:57
  • $\begingroup$ @JesusSalas Never mind my last paragraph, then. (Leaving it here for Googlers.) $\endgroup$ – Raphael Oct 10 '17 at 7:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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