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.
248
questions
2
votes
3answers
160 views
Finding largest elements
I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is
...
0
votes
2answers
37 views
Trouble with Big-O notation proof by definition
Let $a,b>0$. Prove
$\left(\log\left(n\right)\right)^{a}=O\left(n^{b}\right)$.
I'm supposed to find an algorithm to find the log(n) largest elements in an array and return them sorted and explain ...
3
votes
3answers
117 views
Is it true that $ 2^{O(3k)} = 2^{O(k)} $?
Is it true that $ 2^{O(3k)} = 2^{O(k)} $?
But It should be different from $ O(2^{k}) = 2^{O(k)} $ ?
I will be happy for simple explanation.
Thanks.
18
votes
3answers
4k views
Time complexity $O(m+n)$ Vs $O(n)$
Consider this algorithm iterating over $2$ arrays $(A$ and $B)$
size of $ A = n$
size of $ B = m$
Please note that $m \leq n$
The algorithm is as follows
...
-1
votes
2answers
49 views
Big-O-notations and Small-o-notations
$a)$ Determine for all pairs $i$ and $j$, $i,j ∈ \{1, \ldots, 6\}$ whether for the ones given below functions $f_i ∈ O(f_j)$ or $f_i ∈ o(f_j)$ or neither of the two applies as $n → \infty$:
$f_1 = \...
0
votes
1answer
70 views
Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$
Before you downvote, please note that this question is distinct from this similar looking question
I came across the following the problem in "The Introduction to Algorithms" by Cormen et. ...
2
votes
2answers
113 views
Big-O notation for lower bound instead of Big-Omega
In the Wikipedia's Binary search tree, one can read
Traversal requires $O(n)$ time, since it must visit every node.
Since it is question of a lower bound, shouldn't we write
Traversal requires $\...
0
votes
1answer
122 views
How does squaring time complexity imply the same time complexity for multiplying different numbers? Isn't it the other way round?
Found this in solutions of a test as being true
If you can square an n-bit integer in time $O(n \,log \,n)$, then you can multiply two n-bit integers in time $O(n \, log \,n)$.
How does the above ...
2
votes
1answer
18 views
Comparisons of functions, their big-oh and their implications
I don't understand why the $1^{st}$ is false but I think I see why the $2^{nd}$ is true.
If $f(n) = O(n^2)$ and $g(n) = O(n^2)$, then $f(n) = O(g(n))$.
If $f(n) = O(g(n))$ and $g(n) = O(n^2)$, ...
0
votes
1answer
49 views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
1
vote
1answer
41 views
A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $
I am trying to look for an example of a monotonically non-decreasing function $ f(n) $ such that:
$ f(n) \in O(n^2) $ and $ f(n) \notin o(n^2) $ but also $ f(n) \in \Omega(n) $ and $ f(n) \notin \...
1
vote
1answer
94 views
How to solve recurrence of a binary tree
I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.
This function calculates both the height and if its a balanced tree.
...
-4
votes
1answer
296 views
Is squaring easier than multiplication? [duplicate]
Let $T_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T_2(n)$ be the time complexity of computing the product of two $n$-bit integers.
Assuming that addition is ...
1
vote
1answer
56 views
Maximum Subarray Problem - Analyzing best case, worst case, and average case time complexity big o
New to the board, if this is the wrong section I apologize and I will delete it. Will be helpful to be provided correct exchange to guide me through this process of learning.
If you have a given an ...
1
vote
2answers
104 views
Solving constants in the recursive term with master theorem
We are learning how to solve recurrence relations in different ways (Forward Substitution, Backward Substitution, Master Theorem, etc...). I really thought I understood the topic since most of the ...
0
votes
0answers
80 views
Is reduction from Rudrata/Hamiltonian path to Rudrata/Hamiltonian cycle O(1)?
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
0
votes
1answer
131 views
Is O(1) considered polynomial time?
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
2
votes
1answer
107 views
How does knowing the input size make the time complexity of a function constant?
After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.
First, I've noticed ...
0
votes
0answers
66 views
Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$
Lets define function $T(n)$ as
\begin{align*}
T(1) &= T(2) = 1\\
T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\
\end{align*}
Does $T(n)=O(\log(n))$? I have no idea how to ...
0
votes
1answer
65 views
How will Big O be with quantum computers?
I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change ...
1
vote
1answer
174 views
Prove $T(n) = T(\left \lceil{\frac{n}{2}}\right \rceil) + 1 = O(\log(n))$
As the title said, prove $T(n) = T(\left\lceil{\frac{n}{2}}\right\rceil) + 1 = O(\log(n))$
My approach is to find $c, n_0 \in \mathbb{R}_+$ such that:
$$\forall n \geq n_0, T(n) \leq c\log(n) -d \text{...
2
votes
2answers
51 views
How to solve recursion T(n) = T(n/3) + T(2n/3) + n?
$T(n) = T(n/3) + T(2n/3) + n$
How can I solve this recurrence formula?
2
votes
2answers
97 views
Is $\log(n-1) \in \Omega(\log(n))$?
I saw this question Can I simplify log(n+1) before showing that it is in O(log n)? and wanted to know if a similar situation was also true.
Namely, is $\log(n-1) \in \Omega(\log(n))$?
1
vote
3answers
51 views
Is $n \log n$ in $O(n^{1.46-\varepsilon})$?
I am trying to figure out the solution of the recurrence relation
$$T(n) = 5T(n/3) + n \log n$$ using the Master Method.
I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the ...
0
votes
0answers
14 views
How to set up a recurrence relation to analyze number of execution of the basic operation of this algorithm? [duplicate]
This an algorithm to count inversions in an array, this is a divide and conquer algorithm, I ...
0
votes
3answers
50 views
Finding a $g(n)$ so that $f(n) = O(g(n))$
I am having trouble on the following algorithms question:
Given $f(n) = \sum^n_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$.
I know that this means I need to ...
1
vote
1answer
58 views
Problem from the Cormen appendix C 1.13
I am currently working on CLRS 1.13. The idea is to use Stirling's
approximation to prove that
$${2n \choose n} = \frac{2^{2n}}{\sqrt{\pi n}} \left( 1 + O \left( \frac{1}{n} \right) \right)$$
Now ...
1
vote
2answers
56 views
Operations with Asymptotic Notations
I am wondering is anyone has something like a cheatsheet with all the operations between $O(n)$, $\Theta(n)$, $\Omega(n)$, $o(n)$, $\omega(n)$. For example, this is something I don't know how to solve:...
2
votes
1answer
147 views
why quicksort can have a best big o notation of (n log n)
I don't really quite understand why quicksort has a big $O$ notation of $(n \log n)$. I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort.
Also in $(...
1
vote
1answer
52 views
Asymptotic notation between two sets of variables
I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its ...
1
vote
1answer
109 views
Analyzing the Runtime of Shuffling Algorithm
The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m^2)$ time for an input $m$. ...
-2
votes
2answers
102 views
Is there a real life example of algorithm that has running time $\Theta(1)$
I am a CS first year student, and as I was reviewing over the theta notation unit, I saw that $\Theta(1)$ exists. I was wondering if there was any real life example algorithm that has a running time ...
2
votes
2answers
69 views
Big Oh rules - How to argue in case of negative base
Let us say you have a function $C_n = (-2)^n + 2^n$.
It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$.
However, how would I go about arguing ...
8
votes
2answers
1k views
Isn't linear time O(n)?
In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22
Partition needs really linear time, not just $O(n)$ time....
2
votes
2answers
83 views
What do you get when you add $O(n)$ to itself $n$ times?
I was watching this video on Algorithms and counting number of inversions and he mentioned being cautions when $O(n) + O (n) = O(n)$, saying that is not true if you add $O(n)$ to itself $n$ times. Is ...
0
votes
1answer
75 views
How to calculate O-Notation?
I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand;
What I would like to ask, if there is a certain way to find out O-Notation? Actually ...
1
vote
1answer
37 views
What's wrong with this substitution for master's method
I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method:
$$T\left(n\right)=T\left(n-1\right)+n^2$$
I did
$$S\left(2^n\right)=S\left(2^{n-1}\...
0
votes
1answer
53 views
Help with model answer for time complexity
Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n?
I tried to write this in python to ...
0
votes
1answer
34 views
Does $c^n = O(2^n)$ and $log_c(n) = O(log_2(n))$ for any constant $c$?
I thought they did, but recently I tried to express $3^n$ as $k \times 2^n + o(2^n)$ for some constant $k$ but wasn't able to. All I found was $3^n = (\frac{3}{2})^n 2^n$. What am I misunderstanding ...
0
votes
0answers
52 views
Prove that $T(n)=\omega(n)$?
Edit: can someone provide clear answer with all details
Given:
$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$
I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
0
votes
1answer
84 views
How can I find this code block's execution time t(n) and big O notation?
Hello I am a CSE student and this question was in my homework.
...
0
votes
1answer
47 views
Recurrence relations and induction: guessing the right bound
I'm currently dealing with the problem $$T(n)=T(\sqrt{n})+T(n-1)+n$$
This doesn't seem to show any pattern when continously broken down as a whole, but I was able to find the complexity of $$T(n)=T(n-...
1
vote
0answers
44 views
Space usage of recursive functions with no return
Consider an algorithm for reversing a sequence given below:
...
1
vote
1answer
34 views
What is the need for "some constant" times $n$?
I have a question regarding the following sentence:
So we can make the following expressions:
The best case running time of LINEARSEARCH is a constant function $T(n)=a$ OR $Θ(1)$
The worst case ...
1
vote
1answer
36 views
Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)
I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.
Definitions:
Let f,g be functions.
$f(n)\in \mathcal{O}(...
2
votes
1answer
58 views
Big O and Little O
If $a_n = O(n^\alpha)$ and $b_n = o(n^\beta)$, prove that $a_nb_n = o(n^{(\alpha + \beta)})$ and $a_n+b_n = O(\max(n^\alpha, n^\beta))$.
For the part about $a_nb_n = o(n^{(\alpha + \beta)})$, I get ...
1
vote
1answer
274 views
Finding n0, asymptotic analysis
I am attempting a textbook question about asymptotic analysis. The question goes:
**
The number of operations executed by algorithms A and B is 8nlogn and
2n^2, respectively. Determine n0 such that A ...
8
votes
1answer
3k views
Are there any functions with Big O (Busy Beaver(n))?
So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
5
votes
2answers
234 views
Upper bounds for a binomial coefficient
I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $...
1
vote
1answer
130 views
Simplify $O(\min(m, n))$?
I know that $O(\max(m, n)) = O(m + n)$, but is there a similar simplification for $O(\min(m, n))$? It could be $O(n) \cap O(m)$ but it does not simplify the notation that much…
