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.

18 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2
votes
0answers
29 views

Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
1
vote
2answers
59 views

How to determine if given “complex” time complexity is $O(n^2)$?

If a given time complexity, such as these: $(n + \log n) * \sqrt{n+\log n}$ $n * (200 + \log^2 n)$ $(7+n^3)\log(n^5)$ is not determinable by just looking at it whether is it in class $O(n^2)$ or not,...
1
vote
0answers
43 views

Big O notations of some functions

What is the big-O notation of the following functions : $\displaystyle\sum_{i=1}^n \left(\begin{array}{c} n-1\\ i \end{array}\right)\\\\ \displaystyle\sum_{i=1}^{n} \sum_{j=1}^{n-i}(3j)\\\\ n^{\...
1
vote
0answers
30 views

Prove that for all functions g: N -> R>=0, and all numbers a in R>=0, if g in Omega(1) then a + g in Theta(g)

Here is a more readable version of the question: Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \...
0
votes
0answers
43 views

Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$

I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$. Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
0
votes
1answer
27 views

How to prove Big-O when $F(N)$ is even or odd

If I'm given a function $f(n)$ which is for example $4n+1$ when even and $3n^2+2$ when odd and I have to prove or disprove $f(n)$ is $\mathcal O( n^2 )$. Do I have to do $f(n) < c n^2$ for all $n &...
0
votes
0answers
23 views

Balanced vs Unbalanced KD-tree range search/query complexity

I'm currently reading up on the time complexity of the range search/query for an unbalanced KD-tree. I see all these different articles where the same the complexity is O(sqrt(N)) where N is the ...
0
votes
2answers
47 views

Comparing growth of two sums of functions

Does $n+n^4$ grow faster than $n^2+n^3$? If so, why?
0
votes
0answers
63 views

Time Complexity of Tabu Search Algorithm

I am trying to find the time complexity of Tabu Search. But I could not find any resources. Any need is appreciated.
0
votes
0answers
33 views

Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
0
votes
0answers
19 views

Question in regards to how an O(N^3) looks like using while/for loops

would the code below be considered O(N^3)? while (...) { while (...) { } while (...) { } }
0
votes
0answers
74 views

What is the Big theta of $(\log n)^2+2n+4n+\log n + 50$?

$f(n)=(\log n)^2+2n+4n+\log n + 50$ I am trying to mathematically prove that $f(n)$ falls under some time complexity big theta. My guess is that it is $(\log n)^2$ because it is the dominant term. I ...
0
votes
2answers
81 views

Time complexity for concatenating strings

I was going through this piece of code from an algorithms books and something doesn't look clear Please ignore the spelling errors, How does 0(x + 2x + nx) reduce to o(xn^2) ? My analogy, assuming ...
0
votes
0answers
37 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
0answers
32 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
26 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 ...
0
votes
1answer
291 views

heap data structure complexity

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

Analysis of kd-tree, how is the vertical line L's intersect areas equivalent to sqrt(N)?

I'm trying to understand how the number of intersected areas by a vertical line in a KD-tree is equivalent to sqrt(n) If you draw a balanced KD-tree with 7 nodes. And then draw a vertical line l. ...