How do determine Big-O of recursive code?

Question

I have the following code, which is an answer to this question: https://leetcode.com/problems/add-digits/

class Solution {
public:
    int addDigits(int num) {
        if (!num/10)
            return num;

        long d = 1;
        int retVal = 0;

        while(num / d){
            d *= 10;
        }
        for(d; d >= 1; d/=10){
            retVal += num / d;
            num %= d;
        }
        if (retVal > 9)
            retVal = addDigits(retVal);

        return retVal;
    }
};

As a follow-up to this though, I'm trying to determine what the BigO growth is. My first attempt at calculating it came out to be O(n^n) (I assumed since the growth of each depth is directly depended on n every time), which is just depressing. Am I wrong? I hope I'm wrong.

Certainly not O(n^n). Rather something like O(f(n)) where f() is a non-linear function. I'm not very versed with that topic, so sorry I can't actually tell you what f() should look like. — πάντα ῥεῖ
– πάντα ῥεῖ, Commented Jun 16, 2016 at 16:29

Community · Accepted Answer · 2017-05-23 10:29:01Z

2

In this case it's linear O(n) because you call addDigits method recursively without any loop and whatnot once in the method body

More details: Determining complexity for recursive functions (Big O notation)

Update: It's linear from the point of view of that the recursive function is called once. However, in this case, it's not exactly true, because the number of executions barely depends on input parameter.

edited May 23, 2017 at 10:29

CommunityBot

11 silver badge

answered Jun 16, 2016 at 16:16

Andrei Zhytkevich

8,1292 gold badges33 silver badges46 bronze badges

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

1 Comment

kmdreko Over a year ago

but the amount it recurses is not linear with n

Community · Accepted Answer · 2020-06-20 09:12:55Z

2

Let n be the number of digits in base 10 of num. I'd say that

T(1)=O(1)

T(n)=n+T(n') with n' <=n

Which gives us

O(n*n)

But can we do better? Note than the maximum number representable with 2 digits is 99 which reduce in this way 99->18->9.

Note that we can always collapse 10 digits into 2 9999999999->90. For n>10 we can decompose than number in n/10segments of up to 10 digits each and reduce those segments in numbers of 2 digits each to be summed. The sum of n/10 numbers of 2 digits will always have less (or equal) than (n/10)*2 digits. Therefore

T(n)=n+T(n/5) for n>=10

Other base cases with n<10 should be easier. This gives

T(n)=O(1) for n<10

T(n)=n+T(n/5) for n>=10

Solving the recurrence equation gives

O(n) for n>=10

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jun 16, 2016 at 16:35

Lorenzo Belli

1,8494 gold badges26 silver badges47 bronze badges

Comments

πάντα ῥεῖ · Accepted Answer · 2016-06-16 16:34:53Z

1

Looks like it's O(1) for values < 10, and O(n) for any other values.

I'm not well versed enough with the Big-O notation, to give an answer how this would be combined.

Most probably the first part is neclectable in significance, and such the overall time complexity becomes O(n).

answered Jun 16, 2016 at 16:34

πάντα ῥεῖ

88.9k13 gold badges125 silver badges199 bronze badges

Collectives™ on Stack Overflow

How do determine Big-O of recursive code?

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related