The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,006 questions
Filter by
Sorted by
Tagged with
35 views

Represent polynomial time complexity as linearythmic

To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, ...
107 views

Show that $T(2^n) = \Theta(3^n)$ [duplicate]

We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?
535 views

Big-O with nested loops and “variables” in the T(n)

So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code: ...
377 views

Introductory explanation of the Big-Oh properties

I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
28 views

Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?

We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$. I came up with following proof but i dont know it's correct or not. $$g = O(f)$$ $$g \le c_1*f$$ $$h \le c_2*f$$ ...
42 views

Asymptotic bound of a heap's height

Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. ...
67 views

81 views