I got it down to O(n) complexity. I'm not fluent in Python, so this solution is in JavaScript, but it's reads fairly easily (especially if you're familiar with C-like syntax)

function decent(digits) {
    var result = "";
    // First, let's get as few 3s as possible for the least significant digits
    while (digits % 3 !== 0) {
        result += "33333";
        digits -= 5;
        // We've reached a point where digits is still not divisible by 3
        // But we're out of digits, so... Not possible.
        if (digits < 0) {
            return "-1";
        }
    }
    // Here, digits is definitely divisible by 3, so just repeat the 5s
    return "5".repeat(digits) + result;
}

I got it down to \$O(n)\$; complexity. I'm not fluent in Python, so this solution is in JavaScript, but it's reads fairly easily (especially if you're familiar with C-like syntax)

function decent(digits) {
    var result = "";
    // First, let's get as few 3s as possible for the least significant digits
    while (digits % 3 !== 0) {
        result += "33333";
        digits -= 5;
        // We've reached a point where digits is still not divisible by 3
        // But we're out of digits, so... Not possible.
        if (digits < 0) {
            return "-1";
        }
    }
    // Here, digits is definitely divisible by 3, so just repeat the 5s
    return "5".repeat(digits) + result;
}