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.
175
questions
0
votes
0answers
238 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 ...
2
votes
4answers
110 views
Is this big O notation format correct? $3^n = 2^{(O(n))}$
I am completing a university exercise deciding whether big notations are true or false.
I am stuck on this question :
$$3^n = 2^{(O(n))}$$
I want to answer False as the format looks incorrect and ...
3
votes
0answers
39 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 ...
0
votes
2answers
65 views
Need help analyzing the runtime analysis of this algorithm/algorithms in general
This is the algorithm I was trying to find the runtime of (doSomething) -
...
1
vote
1answer
56 views
Determining asymptotic notation of a complex function
$$
5n^4\log{n} - \frac{100n^2}{\log_4(n^2)} + 40
$$
I am currently studying algorithm analysis and i need to express this function in terms of big O, theta and omega, so I should find C, and N0 for ...
1
vote
0answers
37 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
3answers
855 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
1answer
22 views
Asymptotic growth of a function containing a sum
How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails ...
1
vote
1answer
201 views
Time complexity of $O(n)$ loop which has a multiplication ($O(n^2)$) in it
Assume we know that the implementation for the multiplication operator for a language is known to be $O(n^2)$.
Given this pseudocode:
...
0
votes
2answers
145 views
Is this program O(n^2logn) or O(nlog^2(n))?
I was wondering whether this program (I'm using a C syntax, hope it's not an issue) is to be considered $O(n^2 \log(n))$ or $O(n\log^2(n))$ or something else entirely.
...
0
votes
1answer
31 views
Big-O Notation: Runtime Analysis
I have a problem with an exercise, I have to analyze the following
For-Loops
Then I have to write down the explicit notation, my problem is that I don't know how to get the right m.
I tried this
but ...
2
votes
1answer
106 views
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (...
3
votes
1answer
151 views
Is O(n log n) exponential speedup over O(n^2)?
I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
2
votes
1answer
118 views
How to compare n number of m-dimensional points among one another with minimum time complexity?
Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all ...
3
votes
1answer
145 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
450 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
78 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 ...
2
votes
0answers
36 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
121 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(\...
1
vote
1answer
80 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
41 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
39 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
25
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
2answers
77 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 LeetCode quiz. The quiz itself goes like this:
Write a program to find the n-th ugly number. Ugly ...
1
vote
2answers
194 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
78 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
77 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
59 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
36 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
75 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
59 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
48 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
55 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
210 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
51 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
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
49 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
525 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
4k 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
102 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
50 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
349 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
164 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
205 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
60 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
35 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
28 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 ...
5
votes
1answer
89 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
1k 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
24 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.
...
