# 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.

235 questions
Filter by
Sorted by
Tagged with
214 views

### Time complexity of pairs in array double loop

I know, that the following is: O(n^2), ...
69 views

### How to calculate the runtime of a following code?

Could someone explain how to calculate the Big O notation for a runtime of a snippet of a code? ...
44 views

### Big-O of iterating through nested structure

While trying to understand complexity I run into an example of going through records organized in following way: ...
46 views

### big theta prove

Prove that $3n^3 - 6n^2 + 9n - 9\log n \in \Theta(n^3)$ using So, how can I prove this by big theta definition? I don't what I should do with the log function
106 views

### Can $n = O(n^2)$?

I'm reading Data Structures and Algorithms by Goodrich. The explanation that he gives for Big Oh notation is given below: Let $f(n)$ and $g(n)$ be functions mapping positive integers to positive real ...
66 views

### How to calcualte the Big-O complexity of the following algorithm?

I have been trying to calculate the Big-O of the following algorithm and it is coming out to be O(n^5) for me. I don't know what the correct answer is but most of my colleagues are getting O(n^3). <...
1k views

### Big O notation for Average case in Linear search

Average case complexity for linear search is (n+1)/2 i.e, half the size of input n. The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given ...
184 views

### What is the complexity of $i^i$?

What is the complexity of the following algorithm in Big O: for(int i = 2; i < n; i = i^i) { ...do somthing } I'm not sure if there is a valid operator to ...
31 views

### Time complexity about Maximum subarray

I recently came across a function called the strawman algorithm which the pseudo code looks like this: ...
151 views

### Solving unusual recurrence with two variables

I have the following recurrence relation: $$T(n,k) = T(n-1,k)+T(n-1,k+1)$$ With the following base cases (for some given constant $C$): For all $x \leq C$ and for any $k$: $T(x,k)=1$ For all $y \geq C$...
156 views

### How does f(n) < cg(n) specify time?

I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes: $O(g(n)) =$ { $f(n)$ : there exist positive constants $c$ and $n_0$ ...
44 views

### Intro to Algorithms: asymptotic function analysis

I'm reading "Introduction to Algorithms" 3rd edition by Cormen, Leiserson, Rivest, Stein Page 46. The authors place formal upper and lower bounds on a function which is quadratic. Can ...
84 views

### What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
81 views

### How to know if time complexity is O(n+m) or O(n*m)

I'm having difficulty understanding when can we know if the time complexity of an algorithm is n+m or n*m Is the time complexity of the following algo O(n+m) or O(n*m) Can you please point me to a ...
575 views

### Sum rule for Big-O with equal complexity-functions?

One property of the Big-O-notation is the sum rule, which states that when I have two functions $f_1$ and $f_2$ and their corresponding complexity functions are $g_1$ and $g_2$, then the combined ...
46 views

### Complexity Values for Specific Code/Functions

(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
43 views

### How to solve recursion with two separate converges rates

What is the correct way to solve the following recursion: $T(n)=T(\lceil\frac{n}{2}\rceil) + T(n-2)$ Or basically any recursion that has two parts which converge in a different rate. I'm trying to get ...
84 views

### How do you calculate the running time using Big-O notatation?

I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod(): ...
186 views

### What is Big O of a loop with square root inside?

Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code: ...
401 views

### Time complexity of printing prime numbers within a range?

I've written an answer to this question, which asks about the following: What is the time complexity for the given code that prints prime numbers from start to <...
74 views

### Does big-Oh impose an ordered partition on the set of the "usual" functions?

The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not ...
50 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 ...
40 views

### Find position in array where element-wise multiplication with string of 1 and 0s results in max value

I have a sequence of 1s and 0s. For example: $bits = [1, 0, 1, 1, 1, 0]$. I also have an array of positive integers. For example $arr = [12, 23, 4, 6, 8, 0, 24, 72]$. I need to find the index, $i$, in ...
81 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,...
269 views

### Big O vs Big $\Theta$ during coding interview

Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$. From the book "Cracking the coding interview": "...
29 views

### Order notation subtractions in Fibonacci Heap

Can order notation on its own imply: $O(D(n)) + O(t(H)) - t(H) = O(D(n))$ My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0....
23 views

### How to find the square with the highest total sum

I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most. For ...
64 views

### Big O Proof , f(n) = 2n + 1 and I have to prove f(n) is O n^2

If I have $f(n) = 2n + 1$ and I have to prove $f(n) \in O(n^2)$, by proving there exists positive constants $c$ and $n_0$ such that $f(n)<cn^2, \forall n\ge n_0$, can I do this all in one step by ...
50 views

### one for loop wraps 2 indexof method, what is the time efficiency?

I'm confused about how to know the time / space efficiency. If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(...