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

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,004 questions
Filter by
Sorted by
Tagged with
13 views

Can we apply the Master Theorem to the following recurrence?

Our recurrence is $$T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if n>1} \\ 1 & \text{if n=1.} \end{cases}$$ I have identified $a = 1 > 0$, and $b = 2 > 1$...
35 views

How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition \begin{align*} \...
23 views

Bubble sort: how to calculate amount of comparisons and swaps

For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do ...
22 views

12 views

Growth of n/logn vs n^(1+e) [duplicate]

Is $\Theta(\frac{n}{log(n)})$ faster growing function than $\Theta(n^{1+\epsilon})$, where $\epsilon > 0$?
37 views

Derive a while loop (which seemingly have some logarithmic traits) runs in $\Theta(n)$

I know for a fact that algorithm A runs in $\Theta(n)$, but how does one derive that? Algorithm A ...
75 views

How can $\Theta$ and $O$ complexities be different?

From the definition of the $\Theta$-notation, $$f(n)=\Theta(g(n))\\\implies \exists n_0, \exists c_1,c_2\gt 0, \forall n\gt n_0, c_1\cdot g(n)\le f(n)\le c_2\cdot g(n)$$ We can see that the ...
65 views

What constant in the latest fast matrix multiplication is hidden by Big-O notation?

I'm evaluating the theoretical run time of matrix multiplication algorithms as it has improved within the last few decades. Algorithms to solve matrix multiplication run in O(n^w) time, where w has ...
47 views

Does a function that belongs to θ(n) belong to O(n^2)? [closed]

My understanding is that the answer is yes. To be θ(n) implies O(n), which itself implies O(n^2). In other words, a function that is tightly bounded by n is trivially upper-bounded by n^2 as well. ...
41 views

42 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
I want to solve this recursion: $$T(n) = 5T(\frac{n}{5}) + \frac{n}{lg(n)}$$ My attempt and issue: None of the cases for master theorem apply here. I tried using Akra-Bazzi method (https://en....