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
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
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…