รันไทม์บิ๊กทีต้าของลูปเชิงเส้นที่ซ้อนกันสองลูป โดยการทำงานภายในจะครึ่งหนึ่งของจำนวนครั้งสำหรับการวนซ้ำด้านนอกแต่ละครั้ง

ฉันมีปัญหามากกับปัญหาอัลกอริทึมนี้ ฉันควรจะค้นหาการวิเคราะห์ขนาดใหญ่ของอัลกอริทึมต่อไปนี้:

function example(n):
    int j=n
    for i=0;i<n;i++:
        doSomethingA()
        for k=0;k<=j;k++:
            doSomethingB()
        j/=2

แนวทางของฉันคือแบ่งการดำเนินการทั้งหมดของอัลกอริทึมออกเป็นสองส่วน ส่วนหนึ่งที่มีการเรียก doSomethingA() และ doSomethingB() ทั้งคู่ และส่วนที่สองหลังจาก j กลายเป็น 0 และเรียกเฉพาะ doSomethingA() เท่านั้นจนกว่าโปรแกรมจะหยุดทำงาน

ด้วยแนวทางนี้ คุณจะมีส่วนที่ 1 เกิดขึ้นสำหรับการวนซ้ำ Logn ของลูปภายนอก ส่วนส่วนที่ 2 จะเกิดขึ้นสำหรับการวนซ้ำ n-logn ของลูปภายนอก

จำนวนครั้งที่การวิ่งวงในลดลงครึ่งหนึ่งสำหรับการวิ่งแต่ละครั้ง ดังนั้นจำนวนครั้งที่การวิ่งควรเป็น 2n-1. ดังนั้นรันไทม์สำหรับส่วนที่ 1 ควรเป็น (2n-1)*c ซึ่งเป็นค่าคงที่ ฉันไม่แน่ใจว่าสิ่งนี้ถูกต้องหรือไม่

สำหรับส่วนที่ 2 งานภายในลูปจะคงที่เสมอ และการวนซ้ำจะเกิดซ้ำ (n-logn)

เราก็ได้ ((2n-1)+(n-logn))*c

ฉันไม่แน่ใจว่างานที่ฉันทำมานี้ถูกต้องหรือไม่ และไม่แน่ใจว่าจะดำเนินการต่ออย่างไร สัญชาตญาณบอกฉันว่านี่คือ O(n) แต่ฉันไม่แน่ใจว่าจะหาเหตุผลเข้าข้างตนเองในบิ๊กทีต้าได้อย่างไร นอกเหนือจากนั้น อาจเป็นไปได้ว่าแนวทางทั้งหมดของฉันมีข้อบกพร่อง ฉันจะโจมตีคำถามเช่นนี้ได้อย่างไร หากแนวทางของฉันถูกต้อง ฉันควรทำอย่างไรให้เสร็จสิ้น?

ขอบคุณ.