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
0
votes
2answers
88 views

Can't understand the $O$ notation for runtime of algorithms

In my book,the $O$-notation is given as: $$O(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{>0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\leq \alpha g(n)\}$$ ...
0
votes
0answers
30 views

Which is better $n^3\log n$ or $n^3$ [duplicate]

I am confused between $n^3\log n$ and $n^3$. Normally $n\log n$ is better than $n^3$ but what's about $n^3\log n$
1
vote
1answer
22 views

What does n with an index 0 mean in defenition of Theta/Big Omega/ Big-oh notation?

We define theta notation as follows: $\Theta(g(n))$ = {f(n): there are exist $c_1, c_2$ > 0 and $n_0$ such that 0 $\leq$ $c_1$g(n) $\leq$ f(n) $\leq$ $c_2$g(n) for all n > $n_0$}. I found an ...
-1
votes
1answer
47 views

Why 2^(2n+2) not equal to θ(2^2n)?

I'm trying to prove this expression 2^(2n+2) ≠ θ(2^2n)? Firstly 0 <= c1.2^(2n) <= 2^(2n+2) for this n=1 c1=1 is a solution set. For n = ∞, 0 <= ∞.c1 <= ∞ c1=1 is provide it. So omega ...
0
votes
1answer
14 views

How should I evaluate time complexity for matrix if I have a fixed (constant) amount of rows and columns?

Suppose, that I have a four-by-four matrix and I want to print each element of it. ...
3
votes
2answers
200 views

What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?

Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get ...
-2
votes
1answer
52 views

Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)

⌊1/𝑛⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls? ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛) Found ...
0
votes
1answer
56 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
0
votes
3answers
40 views

Can the worst-case analysis of $f(n)$ be $\Omega(g(n))$ but not $O(g(n))$?

I am struggling to wrap my head around using $\Omega$-notation to describe worst-case running time of an algorithm, or $O$-notation to describe the best-case running time. Specifically, I struggle to ...
0
votes
0answers
40 views

Average depth BST upper bound

I have a question regarding the BST average depth upper bound. Following the proof from Data Strucutures and Algorithms in Java by Weiss (3rd edition), I was wondering if there was some kind of ...
1
vote
1answer
28 views

For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of ...
0
votes
2answers
50 views

$(\log n)^{\log n}$ lower-bound and upper-bound

we know that $n \geq \log{n}$ however I understand that $(\log n)^{\log n}$ grows faster than $n$. I have been trying to prove this however I can't seem to figure it out.
1
vote
2answers
50 views

Silly question: what counts as a “unit of work” when computing big-Oh time complexity

I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work". It says in the textbook that certain ...
2
votes
1answer
159 views

Shifted Big Os. How to say O((n+c)!) = O(n!)?

Suppose an algorithm is $O(n!)$, but we need to run it $n$ times, so the total complexity is $nO(n!) = O(n \cdot n!) = O((n+1)! - n!) = O((n+1)!)$ Strictly, there is no constant factor that would make ...
0
votes
1answer
31 views

Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

$f:\mathbb{N} \to \mathbb{N}$ is in $\mathcal{O}(0)$ only if $f(n) \neq 0$ for a finite number of values of $n$. Therefore, $\mathcal{O}(0) \subset \mathcal{O}(1)$ strictly. Is there something in ...
1
vote
1answer
37 views

Big-O notation for Polynomial Time Complexity

Recently we had a quiz where one of the question were - Q: Asymptotic notation for polynomial : - 2^Ο(n) - Ο(n log n) - n^Ο(1) - None of these I know that ...
-3
votes
2answers
75 views

Is $\Omega(n) = O(n \log n)$? [closed]

problem $T(n) = 3T(n/4) + n \log n$ $f(n) = n \log n$ and $g(n) = n$ Why is $\Omega(g(n)) = O(n \log n)$? Is it because $\Omega$ means at some $n$ and constant, $\Omega(g(n)) = O(n \log n)$?
0
votes
2answers
114 views

How to show working for summing of Big O notation

The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed? $$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$
2
votes
3answers
130 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
35 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
116 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
3k 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
45 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
45 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
73 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
47 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
46 views

Asymptotic notation for summations

I am struggling to understand why this property of asymptotic notation is true
1
vote
1answer
36 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
33 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
242 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
35 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
70 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
56 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
76 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
57 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
59 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
42 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
126 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
46 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
66 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
45 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
49 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
54 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
66 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
45 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
88 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
88 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 ...

1
2 3 4 5