0
for(a = c; a > 0; a/=2) 
    for(b=0; b < 2*a; b++)

I have reached the conclusion that this is O(nlogn) runtime but I'm not sure.. My logic is that the outermost for-loop runs logn times as its being divided by 2 every time, and then the innermost for-loop runs 2 times the halved number; therefore it runs n times.

CuriousPerson
  • 37
  • 1
  • 4
  • Possible duplicate of [What would be the tight asymptotic runtime (Big Theta) for these algorithms?](https://stackoverflow.com/questions/52743350/what-would-be-the-tight-asymptotic-runtime-big-theta-for-these-algorithms) – meowgoesthedog Oct 12 '18 at 08:07
  • the easiest way is runnung a sample code. – kelalaka Oct 12 '18 at 17:22

1 Answers1

0
#include <iostream>

int main() {

    int c = 16;

    for(int a = c; a > 0; a/=2) {

        for(int b =0; b < 2*a; b++)
            std::cout << "*";

        std::cout << std::endl;
    }
}

output

********************************
****************
********
****
**
  • In the first inner loop you see, b from 0 to 2*a
  • In the second inner loop you see, b from 0 to 2*(a/2)
  • In the third inner loop you see, b from 0 to 2*(a/4)

sum these: 2a + a + a/2 + ...+1 = 2a -1 \in O(n), since a input size.

kelalaka
  • 5,064
  • 5
  • 27
  • 44
  • Ah I see, that makes sense. Thanks. I just wanted to ask because It seems I am very lost in this topic of time complexity. How should I go about approaching questions like these? Also would it also be Big Theta(n)? – CuriousPerson Oct 12 '18 at 19:04
  • Search and read. Normally your books and professors must define in the lecture. https://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent – kelalaka Oct 12 '18 at 19:06
  • By the way, if the inner loop runs in O(n) time, don't we also have to check what the outer loop runs in? which seems to be O(logn) time, so the runtime complexity of the two for loops nested together would be O(nlogn) right? It would also be Big Theta(nlogn) right? – CuriousPerson Oct 13 '18 at 08:05
  • If you are saying that the inner loop runs totally the answer yes. The first line already contains an amount calculation. therefore > log n. a+a/2+a/4+...+/1 = a-1. therefore result 2a-1 \in O(n). – kelalaka Oct 13 '18 at 08:56