A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [big-o-notation]

Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation.

Filter by
Sorted by
Tagged with
3
votes
1answer
55 views

Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

Given two algorithms with their time-complexity $t_a(n)=\sqrt{n}$ and $t_b(n) = 2^{\sqrt{\log _{2}n}}$ and i have to show $t_b(n) = O(t_a(n)) $. I´ve made a program to check this statement and it ...
2
votes
2answers
184 views

Why is n log n dominated by n log^2 n?

Does the rule of $n ^ a$ dominate $n ^ b$ if $a > b$ apply here as well? My understanding is that $n \log n$ will be dominated by $n \log ^2 n$ because of $\log$ being raised to the power of $2$.
1
vote
1answer
43 views

About Big O properties

Suppose I have something like the following: $f(x) = g(x) + O(x^n)$ And I apply a power $m$ to both sides $f(x)^m = g(x)^m + \cdots + O(x^n)^m$ My question is whether the following is well ...
1
vote
0answers
33 views

Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate]

How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
4
votes
1answer
99 views

Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

Suppose I have an algorithm whose running time is $O(f(n))$ where $f(n) = O\left(\frac{\log n}{\log\log n}\right)$ And suppose I can change this running time in $O(1)$ steps into $O\left(f\left(\...
2
votes
1answer
61 views

How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a ...
0
votes
0answers
35 views

Summing big-O-notation

prove or disprove $$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$ I have no idea about where to begin. what are the theories which should be used here?
0
votes
1answer
30 views

How does $n^c \lg n, 0<c<1$ compare to other common time complexities

Between what two common time complexities would you place $n^c lg n, 0<c<1$? The following table illustrates the common time complexities. Source: wikipedia
24
votes
2answers
4k views

Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
0
votes
1answer
28 views

Big-O notation for the given function whose runtime complexity grows faster than the input

I struggle to determine the runtime complexity of a function I thought of while trying to solve this quiz. The quiz itself goes like this: Write a program to find the n-th ugly number. Ugly numbers ...
1
vote
2answers
39 views

Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$ \sum_{k=1}^{n-1} O(n). $$
4
votes
1answer
76 views

Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

I am trying to understand the asymptotics of \begin{equation} f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})} \end{equation} In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
2
votes
2answers
56 views

How to determine time complexity with a simple way?

I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−...
2
votes
1answer
55 views

Show that the union of Θ and o is not O

Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$ I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would ...
2
votes
0answers
33 views

Difference Between $n^{\Omega{(1)}}$ and $\Omega{(n)}$ [closed]

I am not sure about the difference between $n^{\Omega(1)}$ and $\Omega(n)$. It seems to me that the only difference is that $n^{\Omega(1)}$ can contain some sublinear functions, i.e., $n^{\frac{1}{2}}$...
3
votes
1answer
40 views

Combining Predicate Logic and BigO

I am a beginner to predicate logic and BigO and am having though time understanding the definition of BigO in terms of predicate logic in the picture attached. I particularly am unable to understand ...
1
vote
1answer
38 views

Is log(n) equivalent to (log(n))^x for big-O analysis?

My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis. ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$ From the ...
0
votes
1answer
46 views

Simplifying this expression with big O when several variables are involved

I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows : \begin{...
1
vote
1answer
50 views

Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
3
votes
3answers
175 views

Find the error in the following “proof” that $O(n) = O(n^2)$

Let $f(n) = n^2 , g(n) = n$, and $h(n) = g(n)−f(n)$. It is clear that $h(n) ≤ g(n) ≤ f(n)$ for all $n ≥ 0$. Therefore, $f (n) = \max(f (n), h(n))$. Thus, $O(n) = O(g(n)) = O(f(n) + h(n)) = O(\max(f(n),...
3
votes
1answer
45 views

Compare log^k(n) with n^(1/2)

I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k > 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that: $$\lim_{n \...
0
votes
0answers
15 views

What is the difference between $\ Ω $ , $\ Θ $ , and O , [duplicate]

What are these difference $\ Ω $ , $\ Θ $ and O ? Why $\ n^3 + 4n^2 = Ω(n^2) $ But, $\ n^3 + 4n^2 = O(n^5) $
0
votes
0answers
14 views

Big Oh Notation Complexity [duplicate]

How it can possible $\ 1/2n^2 -3n = Θ(n^2) $ Why we dont care $\ 3n $ and $\ 1/2 $
0
votes
1answer
46 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 ...
0
votes
2answers
74 views

Time-complexity for basic multiplication and division algorithms

The algorithms below has been taken from Discrete Mathematics and it's Applications 7th edition book by Rosen. p.253 says that "number of shifts required is $O(n^2)$" and "a total of $O(n^2)$ ...
1
vote
1answer
173 views

Solving the recurrence relation T(n) = 2T(n/2) + nlog n via summation

I have seen a few examples of using the master theorem on this to obtain O(n*log^2(n)) as an answer. I am trying to solve this by unrolling and solving the summation, but I can't seem to get the same ...
2
votes
3answers
95 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 ...
-1
votes
1answer
42 views

confused with Time Complexity [duplicate]

I was reading book related to Time Complexity, and came up with 4 lines of equations that I could not understand properly, could you please explain why are those true? 1) $n = o(n\log\log n)$ 2) $...
0
votes
2answers
112 views

Runtime complexity of a brute force factoring algorithm? (in terms of bits)

Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
0
votes
3answers
159 views

How to prove that ($56n^2+106n+48)(\log(264n^2+200)) = Θ(𝑛^2\log n)$

I understand that essentially we have to prove that $$c_1(n^2\log n)\le (56n^2+106n+48)(\log(264n^2+200)) \le c_2(n^2\log n)\,.$$ I am confused on how to simplify this further? And ...
1
vote
1answer
50 views

How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

We can learn the big-O of building a binary heap using recursive method is O(n log n) from wiki "This approach, called Williams’ method after the inventor of binary heaps, is easily seen to run in O(n ...
1
vote
1answer
32 views

Complexity analysis using big - O, Omega and Theta notation

I was reading a research paper and there I read the following: $t=O\left(d^{2} \log _{d}^{2} n\right)$ matches the lower bound $\Omega\left(d^{2} \log _{d} n\right)$ in the regime where $d=\Theta\...
0
votes
0answers
27 views

How to find running time complexity of divide and conquer method without Master Theorem

I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
0
votes
0answers
23 views

Asymptotics and logarithms/exponents

We have four categories: additive constants, multiplicative constants, polynomials, and exponentials When determining the growth order of functions, we only care about polynomials and ...
4
votes
1answer
74 views

Exact meaning of $2^{\mathcal{O}(f(n))}$

In Sipser's Introduction to the Theory of Computation he uses the notation $2^{\mathcal{O}(f(n))}$ to denote some asymptotic running time. For example he says that the running time of a single-tape ...
1
vote
3answers
287 views

Why is heap insert O(logN) instead O(n) when you use an array?

I am studying about the arrays vs heap for make a priority queue For check the heap implementation I am reviewing this code: Heap , but I have the following question. Heap is based on array, and ...
2
votes
1answer
19 views

Asymptotic Relationship from Limit

F(n) = n-100 G(n) = n-200 I am trying to show the asymptotic relationship between these two functions using limits. I take the limit n->∞ f(n) / g(n) and I get the result 1 which is constant c. ...
-2
votes
1answer
29 views

Help with Big-O homework [duplicate]

"er" is the Danish equivalent of "is" in English. I need some help with the square root one. Additionally, it would be nice to know if the other ones are correct.
0
votes
1answer
97 views

heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
0
votes
1answer
44 views

Helping prove this notation for Big-O(n!)

Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is ...
2
votes
2answers
106 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
4
votes
1answer
592 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
3
votes
2answers
58 views

Struggling to understand the symbolism around the big oh formal definition

I'm struggling to understand what exactly T(n), and f(n) is in the above text: When we compute the time complexity T(n) of an ...
2
votes
1answer
54 views

Time complexity, Big-O for this function?

def f(n): if n < 100000: return 0; for(int i = 0; i < n*n; i++){ return f(n-1) } What is the time complexity? My answer is $O((...
1
vote
1answer
30 views

Asymptotic notation and random variables

I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values). Suppose that the two ...
0
votes
2answers
83 views

How to find i-th root of n whose remainder is the smallest?

Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively ...
3
votes
1answer
53 views

How to calculate Big O of $T(n) = aT(n^b) + f(n)$?

I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or $O(n^{\log_b{a}} + f(n))$ Today I was faced with $T(n) = T(\sqrt n)...
0
votes
0answers
39 views

$\Omega$-notation for insertion sort [duplicate]

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...
0
votes
0answers
27 views

Splay tree amortized cost analysis

I am looking into the amortized analysis of splay trees and seem to be missing something. Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part ...
-3
votes
2answers
218 views

BigO time complexity of 3 nested for loops

I'm debating with a friend whether a particular function I wrote is $O(N^3)$ or $O(N \times M \times X)$ I believe it is the latter since all 3 variables differ in size. $N = 100, M = 50, X = 10000$ ...