Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail?

I am working with the median-median algorithm or BFPRT algorithm and I seek to understand why would the partition of the array by $ 7$ blocks would work but with the $ 3$ fail?

If we divide into blocks of $ 7$ then we will get: Solving it by substitution I think the following manner: It is a recursive tree. In the worst case it takes $ T(10n/14)$ time. So in the worst case it goes down to the bottom by $ (10/14)^kn=1$ steps; $ k=log_{14/10}n$ . At each level of recursive tree the total cost is $ \le cn$ for some constant $ c$ . So by the simplified assumptions using substitution $ k < n$ $ T(n)\le dn \log(n)$

$ T(n) \le T(n / 7) + T(10n / 14) + O(n) \le d\frac{n}{7}lg(n/7)+d\frac{10n}{14}lg(10n/14)+cn \le d(\frac{n}{7}lgn – \frac{n}{7}lg7) + d(\frac{10n}{14}lgn – \frac{10n}{14}lg10/14) + cn = d\frac{12n}{14}lgn – d\frac{n}{7}lg7 – d\frac{10n}{14}lg\frac{10}{14} + cn=d\frac{12n}{14}lgn – d\frac{n}{7}lg7 – d\frac{10n}{14}lg10 – d\frac{10n}{14}lg14 + cn \le d\frac{12n}{14}lgn + cn$

So, $ T(n) = O(nlgn)$

The same way for blocks of size $ 3$ .

$ T(n) \le T(n / 3) + T(2n / 3) + O(n)$ we get $ T(n) = O(nlgn)$

Now, how to show that $ T(n)$ for 7 is also $ O(n)$ and for 3 it can not be $ O(n)$ . Also, in general how can I guess that the $ T(n)$ is also $ O(n)$ because here in both cases my thoughts are they both $ O(nlogn)$ ?

How to resize partition to use non-contiguous free space?

I have the following partition setup (windows 10/ubuntu 18.04 dual boot).

I would like to extend my ‘ubuntu-root’ partition to use all of the ~97GB of unallocated space but I am unable to do so as the memory is not contiguous I believe. I have seen some posts similar to this saying that the swap partition can be deleted to allow for this to happen? I am relatively inexperienced in setting up partitions so I want to do this in the least destructive way.

Any help would be greatly appreciated!

Restore ESP partition after accidental format

While installing a new SSD to my Ubuntu server I have made the grave mistake of formatting a partition on the wrong drive. I’ve accidentally formatted the ESP partition of my HDD that contains the OS. This has lead to Ubuntu not booting at all anymore and the PC just telling me reboot and select proper boot device.

I’ve googled all around, find posts telling me to use the Ubuntu Live usb and select “Rescue a broken system”, but those posts are all very old and neither the Ubuntu server nor normal image show me that option. I’m writing the images with Rufus as GPT so I’m able to boot the usb through UEFI. Another post mentioned selecting “reinstall ubuntu” after selecting “install ubuntu” but I don’t have that option.

I’ve tried boot repair both through Ubuntu live usb and as standalone live usb, but it returns 3 commands of which the last one fails. After I click continue it tells me grub is still present and to try again. I googled that too and they recommended editing the last command, but that didn’t work either.

Could someone point me in the right direction and tell me if this is even possible? It’s 5 am and I’ve been at this for 4 hours straight trying to get my server back up and running, hope my explanation is clear enough.

How to Increase Root Partition

I put an Image of Ubuntu 18.04.3 onto a 32GB SD card. It came with no desktop, so I am trying to install xubuntu. When I try to install it using sudo apt-get install xubuntu-desktop I get the following error: You don't have enough free space in /var/cache/apt/archives

I tried sudo apt-get autoclean sudo apt-get clean and different variants of sudo apt-get autoremove but nothing worked.

Results of df -h are the following

Filesystem Size Used Avail Use% Mounted on /dev/root 2.1G 1.4G 513M 74% / devtmpfs 1.9G 0 1.9G 0% /dev tmpfs 1.9B 0 1.9G 0% /dev/shm tmpfs 1.9G 2.5M 1.9G 1% /run tmpfs 5.0M 0 5.0M 0% /run/lock tmpfs 1.9G 0 1.9G 0% /sys/fs/cgroup /dev/mmcblk0p1 253M 29M 224M 12% /boot/firmware tmpfs 381M 0 381M 0% /run/user/1000

I’m new to linux, but why is my root (and filesystem in general) so small if my SD card is 32GB? And is there a way to increase root through the command line(maybe fdisk)? I don’t have another linux machine that I can run Gparted on. But I do have a Windows laptop that could possibly do Gparted Live. I’ve never done that before so if that is the best solution, tips to get started would be much appreciated.

Don’t know if it matters but I’m following the instructions hereRaspberry Pi 4 Ubuntu Server/ Desktop 18.04.3 Image (unofficial) to try and get Ubuntu up and running xubuntu on my Rpi 4.


Results of sudo parted -ls are the following

Model: SD SK32G (sd/mmc) Disk /dev/mmcblk0: 31.98GB Sector size (logical/physical): 512B/512B Partition Table: msdos Disk Flags:  Number  Start     End     Size   Type     File System    Flags 1       1049kB   269MB   268MB   primary    fat32        boot,lba 2       269MB   31.9GB   31.6GB  primary    ext4      

I need to partition ubuntu 18.04 on both ssd and hdd,i have 240 gb ssd and 2tb hdd,i already installed on ssd but my hdd is not used

i need help, i can reinstall also, but i need ssd for boot and other things and hdd for data and storage, please help me . I hope there is a way without restarting the whole procedure,even if there is not please help me.Thanks in advance

I can’t install Ubuntu because of a problem related to partition alignment?

The hard disk of my computer failed, so I bought a new external hard disk, to install Ubuntu on it, and let me use my computer.

I have experience installing Ubuntu in a USB flash memory,

So I followed those steps and everything was going fine until in the window of partition menu I pressed the “Install Now” button.

Data: My new HDD is of one tera, “Adata” is the brand, it is connected by a USB cable.

It appeared the following warning:

The partition /dev/adb5 assigned to / starts at an offset of 2048 bytes from the minimum alignment for this disk, which may lead to very poor performance. Since you are formatting this partition, you should correct this problem now by realign the partition, as it will be difficult to change later, to do this go back to the main partition menu, delete the partition, and recreate it in the same position with the same settings. This will cause the partition to start at a point best suited for this disk.

There were also three buttons: “x”, “cancel” and “accept”. Whichever I click on it returns me to the partition menu.

I do as the message says: I erase all the partitions and created a new one using it as / but that doesn’t solves the problem, and the warning appears again, I do not know what I am doing wrong.

Using the program gparted is not helping nor working at all.

I would like to install it although it would have a low performance, but it doesn’t let me.

I’ve been also creating two or more partitions, for example I created one of the size of half of the disk and the second of the rest of the size, this changes the offset bytes number that appears in the warning, but that does not solve the problem.

Safest option for resizing /home and merging newly freed space with existing free space to form shared partition

I have Ubuntu 18.04.2 installed in the dual-boot mode along with Windows 10, and here is my current partition setup.

enter image description here

What I’d like to do is install Ubuntu 18.04.4 afresh while resizing my /home partition to, say, 4 GB (is this a reasonable size? I do not plan on storing any large files such as audio/video ones) and then combining the freed space with the 2.36 GB currently unallocated to create a shared NTFS partition.

What is my best (safest) course of action? Should I carry out the partition resizing and partition creation steps before I install Ubuntu 18.04.4? I believe I can do this by booting using a gparted live USB. Then, I could just install 18.0.4 on the existing / partition while formatting it and the newly resized /home. Is this the right way to do it?

Or will I get a chance to make these changes at the time of the installation of the OS? I have not clicked beyond this screen during the installation process and do not whether the above will be an option.

enter image description here

Changing the name of the Ubuntu partition?

I know the procedure for changing the label of a volume: open GParted, click the disk, right click the partition, select Label File System. But when I try to apply the procedure to the partition that contains Ubuntu, Label File System is disabled.

Is this just because Ubuntu is running from that partition, or is there a more sinister reason? That is, if I boot a live Ubuntu and label the partition from there, will it work just fine, or will it damage my Ubuntu installation?

Computer stuck in “System BootOrder not found” loop following partition resize

Just made a rather fatal late night mistake. I booted into gparted live and shrunk my / partition, then enlarged my /home partition to give myself some more space. After applying these changes and restarting, my computer was caught in a boot loop, displaying the following:

System BootOrder not found. Initializing defaults. Creating boot entry "Boot0000" with label "ubuntu" for file "\EFI\ubuntu\shiux64.efi"  Reset System 

After this, the computer shuts down, starts up, shows this message, and repeat.

All the information I’ve found on fixing this involves booting from a live USB, or messing around in BIOS, but it looks like I even get to my BIOS to try anything. The system doesn’t respond to any keystrokes, and shuts down immediately after displaying the above message. Does anyone have any suggestions?

The laptop I murdered is the HP Spectre 13-v110ca – i5 7200U