Why digit_add Is Theta of log n, and Stopping Early Is Still Linear

Why does looping over the digits of n cost only log n, and why doesn't stopping a search early change its worst case?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Add digits by dividing by ten

The video showed that taking the last digit of n is the same as dividing by 10 and keeping the remainder: 4271 gives remainder 1 and leaves 427. Write digit_sum(n) for an int n >= 0 that adds up the digits of n without converting it to a string, peeling off one digit per pass of a while loop. You may find % and // useful. Define digit_sum(n).

def digit_sum(n):
    """ assume n an int >= 0; no str() allowed """
    # peel off one digit per pass and add it to a running total
    return ...

def digit_sum(n):
    """ assume n an int >= 0; no str() allowed """
    # peel off one digit per pass and add it to a running total
    return ...

Python runs in your browser

⌘/Ctrl + Enter runs

returns an int

matches the video's two examples

handles 0 and numbers with zeros inside

agrees with the string version on many inputs

←Previous Two Calls Per Call: Recursive Fibonacci and the Cost of All Subsets Next Same Bisection, Two Thetas: Slicing Copies, and When Sorting Pays Off →