What is the time complexity of the given code?

Question

While(n>=1)
{
    n=n/20;
    n=n/6;
    n=10×n;
    n=n-10000;
}

I tried like this =>

In this loop, N gets reduced by N/12 - 10000. so, time complexity is O(log N).

If you have an idea what the complexity might be, you can calculate concrete values for some n and compare the resulting graph with the assumed complexity. If both graphs are similar, you can start to find a prove why your assumption is correct. — MrSmith42, Sep 05 '16 at 08:07
Please don't post what is basically the same question every few hours (http://stackoverflow.com/questions/39324836/what-is-the-time-complexity-of-given-code). You may want to read a more general Q&A first, like: http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm — m69's been on strike for years, Sep 05 '16 at 12:15

score 6 · Accepted Answer · answered Sep 05 '16 at 07:34

6

That seems to be correct. If this is an exercise, you should be prepared to argue why O(log_12(N))is O(log(N)).

answered Sep 05 '16 at 07:34

mort

1

Bases of logarithms are immaterial in order of growth: logarithms to different bases differ by constant factors – Garrick Sep 05 '16 at 07:36
1

Yes, but can you prove that mathematically? – mort Sep 05 '16 at 07:43
I don't know where I get wrong but why isn't it `O(log(N+constant))`? – YiFei Sep 05 '16 at 07:46
2

@mort, Log base 12 (N) = log base 2 (N) / log base 2 (12) , which simplifies to log base 2 (N) – Garrick Sep 05 '16 at 07:54
2

@stackuser: yeah, that's it – mort Sep 05 '16 at 08:24
1

@YiFei: The constant is substracted, i.e., it's `O(log(N - constant))`, which is trivially `O(log(N))`. – mort Sep 05 '16 at 09:01

1 Answers1