CODEWITHSUNDEEP
ccomplexity-theory
user1980750
user1980750

Reputation: 693

Time Complexity C

void f(int n) {
 int x = n;
 while (x * x > n) {
   x /= 2;
   printf (“x cubed = %d\n”, x * x * x);
 }
 while (x > 0)
   x--;
 printf("hello %d\n", x);
}

I don't understan how they got complexity of TETA(sqrt(n))... can someone explain me the formal way how to find complexity of this alghorithem, and others like this..? do I need to make a Tracking table? is there any site that gives examples on alghorithems and there complexities?

10x a lot!

Upvotes: 2

Views: 519

Answers (1)

Ivaylo Strandjev
Ivaylo Strandjev

Reputation: 70929

When you exit the first while cycle:

 while (x * x > n) {
   x /= 2;
   printf (“x cubed = %d\n”, x * x * x);
 }

You will have x in the interval [sqrt(n)/2, sqrt(n)] and after that you execute x iterations of the next cycle. First cycle has complexity of the order of log(n) and thus the overall complexity is theta of sqrt(n) as defined by the second cycle(log(n) grows slower than sqrt(n)).

Upvotes: 3

Related Questions